OpenAI 수학 저장소의 빠른 푸리에 변환 주장, 빅오 표기 악용이라는 비판

이건 나쁜 글이라고 봄. 저자가 이론 쪽을 악의적으로 본다는 게 문제임. STOC, FOCS, SODA는 실용 알고리즘 하는 데가 아님. 실용적인 걸 원하면 ESA나 ALENEX, VLDB/SIGMOD 가면 됨.

실용 성능 신경 안 쓰는 알고리즘 연구를 왜 봐야 하냐는 말도 일리 있음. 빅오 대신 덜 악용되는 기준을 만드는 게 더 낫지 않나 싶음.

'악의'는 과하다고 생각하는데 '악용'은 맞는 말 같음. 임의 정밀도 산술이 필요해서 물리적으로 구현 못 하는 복잡도 결과는 쓸모가 없다고 봄.

이론가 입장에서 말하면 갈락틱 상수에 별로 신경 안 쓰는 건 맞는데, 연산 모델은 진짜 중요함. 빅오 안의 상수도 상수 시간 연산을 뭘로 보느냐에 따라 상수가 아님.

외부인 입장에서 궁금한데, 이 분야 논문은 보통 정확한 복소수 산술을 전제로 함? 튜링 머신 같은 모델을 쓰는 줄 알았음.

튜링 머신은 복잡도에선 거의 안 씀. P vs NP 정도에서나 쓰고, 선형이랑 이차를 구분할 때는 실제 컴퓨터랑 가까운 모델이 필요함.

비트 길이에 대해선 선형이고 크기 기준으로는 지수적일 수 있음. 초록에도 길이 n이라고 적혀 있음. 복잡도에선 흔한 얘기임.

FFT 주장은 잘 모르겠는데, 다중 테이프 튜링 머신에서 n log n 곱셈 주장은 실제 램보다 더 제약적인 모델임. 그래도 갈락틱인 건 똑같음.

지금 integer-mult-bounds 저장소에서 상한을 낮추려고 여럿이 달라붙고 있음. kappa 값이 0.001635 근처까지 나온 상태임.

그 저장소 PR이 508개, 커밋이 408개 쌓였다고 하더라. 추가 속도가 미쳤음.

코딩 면접 리트코드 생각남. ASCII 문자 공간을 상수 시간으로 치는 문제들이 있는데, 이것도 비슷한 냄새가 남.

빅오로 쓰는 게 여기선 별로임. 보통은 복소수 덧셈이랑 곱셈 횟수로 세는 게 맞음.

수학자 무시하는 감정이 AI 증오랑 섞여서 나오는 게 씁쓸함. 근데 무시까진 아니고 원래 있던 가벼운 무시 정도 같음.