OpenAI가 주장하는 더 빠른 푸리에 변환의 수학 살펴보기

여기 반응이 좀 혼란스러움. 이론을 현실로 옮기는 첫걸음 아닌가? 더 큰 수를 곱할 수 있다면 FT가 빨라질 수 있고, 이제 질문은 가능 여부에서 이를 실행할 하드웨어가 있는지로 옮겨간 것 아닌가?
내 전문 분야는 아니라서, 왜 현재 명령어가 처리할 수 있는 크기의 한계로 볼 수 없는지 궁금함. 128비트 시스템이면 유의미하게 달라질까?

잘못된 비판임. 처음 듣는 “slopository”라는 신조어는 반갑지만, 이론 연구자에 대한 악의는 비판해야겠음. STOC/FOCS/SODA는 실용적인 알고리즘을 다루는 학회가 아님. 그런 연구를 원하면 ESA, ALENEX, VLDB/SIGMOD 같은 응용 중심 학회를 보면 됨.
실험을 하지 않는다는 이유로 이론을 깎아내리는 건 부당함. 이들은 수학자이며, 빅오의 상수가 터무니없이 커도 상수라면 괜찮음. 이렇게 생각하면서도 Ben이 대단한 사람이라고 평가할 수 있음.

이론 연구자로서 천문학적으로 큰 상수에 “관심이 없다”는 건 어느 정도 맞음. 철학적인 이유로 계산의 구조에 관심이 있지만, 계산 모형은 정말 중요하게 봄.
달리 말하면 빅오 안의 상수는 완전히 고정된 상수가 아님. 어떤 연산을 상수 시간으로 가정하느냐에 따라 달라짐.

알고리즘 이론가들이 실용적인 성능에 관심이 없다면, 우리가 그 연구에 관심을 가져야 할 이유는 무엇인가? 다른 누구에게도 흥미롭지 않은 기묘한 놀이일 뿐임.
천문학적 규모에서나 쓸 만한 알고리즘을 더 만드는 대신, 편법의 여지가 적은 빅오의 대안을 만들고 이론가들이 그 규칙을 따르게 하는 편이 더 유용해 보임.

논지 전체를 읽으면 충분히 납득됨. 알고리즘의 점근적 복잡도를 측정하는 허술한 관행도 함께 풍자하는 글임.
시간 복잡도 계산은 상수를 무시함. 알고리즘 A에 10^10 + n번, B에 n^2번의 반복이 필요하면 이론적으로는 B가 더 나쁘지만, 실제로는 A가 유용해지기까지 한참 기다려야 함.
시간 복잡도는 규모가 커질 때 얼마나 잘 확장되는지는 알려줘도, 시작부터 우주가 끝날 때까지 기다려야 하는지는 알려주지 않음.

“악의적”이라는 표현은 과하지만, 허점을 이용했다는 평가는 타당하다고 봄. 실용적 관련성이 생길 가능성조차 없는 이론은 쓸모없으며, 어떤 물리적 시스템으로도 구현할 수 없는 임의 정밀도 연산에 의존하는 계산 복잡도 결과가 여기에 해당한다고 봄.

글쓴이는 이론적 알고리즘 설계 분야 전반을 쓸모없다고 공격함. 그 논리를 끝까지 밀면, 최악의 경우에도 O(n)에 중앙값을 찾는 중앙값들의 중앙값(median of medians) 처럼 알고리즘 설계 수업에서 배우는 기법도 실무에서 쓰이지 않는다는 이유로 쓸모없어짐. 정수 곱셈이 O(n log n)에 가능함을 보인 2019년 Harvey–van der Hoeven 결과 역시 천문학적 오버헤드 때문에 응용처가 없음.
글은 이론이 원래 질문과 동떨어져 미해결 문제가 학계의 지위 경쟁용 퍼즐이 됐다고 비판하지만, 컴퓨터 과학이 컴퓨터 자체와 별 관계가 없다는 건 신입생에게도 흔히 알려주는 사실임. 튜링 기계와 결정 가능성은 본질적으로 수학적이며, Wang 타일링의 결정 불가능성도 컴퓨터와 직접 관계없는 중요한 컴퓨터 과학 성과임.
“천문학이 망원경에 관한 학문이 아니듯 컴퓨터 과학도 컴퓨터에 관한 학문이 아니다”라는 Dijkstra의 말도 유명함. MIT 공개 강의에도 관련 장면이 있음:

.

글의 핵심은 그보다 더 강한 데 있다고 봄. 알고리즘은 크기가 n에 대해 초다항적으로 증가하는 복소수를 곱해야 하며, 글에 따르면 비트로 저장할 경우 메모리 요구량이 사실상 입력 길이에 대해 지수적이 됨. 그런데 그런 임의 크기 복소수의 곱셈을 단일 연산으로 가정함.
임의 정밀도 산술식을 상수 시간에 실행하는 오라클이 있다고 생각하면 됨. 온갖 계산을 그 안에 인코딩해 현실에서는 불가능한 알고리즘을 실행할 수 있음.

중앙값들의 중앙값이 실무에 쓰이지 않는다는 건 사실이 아님. 주석이 충실한 Go 코드 255줄로 구현한 예가 있음: https://github.com/ncruces/sort/blob/v1.0.3/quick/quick.go.
최악의 경우에도 선형 시간이며, 정렬에 활용하면 평균·최악의 경우 Go 표준 라이브러리보다 빠르고 최선의 경우에만 조금 뒤처짐. 내 경험상 median-of-medians보다 약간 복잡한 median-on-ninthers는 성능이 악화되는 입력의 대체 처리 수단으로 힙 정렬과 특히 힙 선택보다 확실히 빠름.
학술적인 이야기만도 아님. 직장에서 정렬을 부분 정렬이나 선택 알고리즘으로 바꿔 중요한 작업의 속도를 높였음.

아이러니하게도 Dijkstra는 컴퓨터 과학에 기반한 기초과학적 관점에서 프로그래밍을 어떻게 해야 하는지 깊이 고민했지만, 업계는 그런 발전된 발상을 실천하는 면에서 여전히 석기·청동기 시대 수준임.

멋진 이론이지만, 그래도 학문 이름은 “컴퓨터 과학”임. 전문가는 아니지만, 망원경으로 천문학 연구를 하려면 망원경이 실제로 어떻게 작동하는지 아는 게 유용할 때가 많을 것 같음.

글에서 AI를 완전히 빼도 같은 결론에 도달할 수 있음. 글쓴이는 그냥 이론 컴퓨터 과학을 정말 싫어하는 것 같음. 이 분야가 과학보다는 수학의 일부라는 건 괜찮지만, 이름부터 “이론”인 분야를 비실용적이라고 일축하는 건 우스움.

그건 글을 최대한 호의적으로 해석한 독해가 아니라고 봄. 핵심은 인간의 이해와 판단을 위해 형성된 불완전한 규칙 아래에서, 인간과 비용·편익 구조가 전혀 다른 기계가 출판·평가 체계를 공략하면 수학과 이론 컴퓨터 과학에 어떤 일이 생기느냐임.
지금은 낭비처럼 보이는 이론 연구가 나중에 유용해질 수 있다는 오래된 논의도 인간의 노력과 역량의 비율을 전제로 함. AI가 만든 방대한 결과도 인간에게 의미가 있으려면 결국 인간의 시간과 노력 예산 안에서 평가해야 함.
공짜 토큰을 가진 누군가의 보상 해킹일지도 모르는 결과를 평생 검토하게 되기 전에, 이것이 스팸인지 유효한 연구인지 따져보자는 것임.

낚시성 글임. 글쓴이는 빅오의 정의가 마음에 들지 않는 것이고, OpenAI는 희생양일 뿐임.

지난주 크게 소개된 계산 복잡도 성과들이 모두 정확한 복소수 산술 모형을 썼다는 걸 몰랐음. 이 분야 논문에서 정확한 복소수 산술이나 정확한 실수 산술을 가정하는 게 흔한가? 외부인으로서는 주로 튜링 기계와 동등한 모형에 관심을 가질 줄 알았음.
여기서 동등하다는 건 실수를 직접 다루는 게 아니라 정수를 대상으로 동작하는 범용 레지스터 기계를 뜻함.

복잡도 이론에서 튜링 기계를 쓰는 사람은 거의 없음. P 대 NP 같은 문제에서는 레지스터 기계보다 “고작” 다항식 배 느리므로 사용해도 상관없음.
하지만 실제 컴퓨터와 비슷한 환경에서 선형 시간과 이차 시간을 비교하려면 튜링 기계는 적절한 모형이 아님.

튜링 기계는 계산 가능성을 다루기에는 좋지만, 복잡도를 다루기에는 그리 좋은 모형이 아님.

이 유사 FFT는 DFT와 곱셈의 알고리즘적 유사성을 이용해 DFT 작업 일부를 곱셈으로 옮기고, 정확한 산술 모형에서는 그 곱셈을 O(1)로 처리하는 것인가?
그렇다면 곱하는 수의 크기가 DFT 문제 크기 n에 대해 초다항적으로 커지는 건, 로봇이 그 안에 작업을 밀어 넣고 오라클처럼 쓰기 때문인 셈임. 여기까지 이해한 게 맞나? 멋진 꼼수임.

이 저장소의 활동량이 놀라움. 커밋 408개에 PR 508개라니, 무슨 일이 벌어지는 건가? 수많은 기여자가 엄청난 속도로 내용을 추가하고 있음.

이 대목에서 웃음이 터졌음. “논문을 읽었냐고? 당연히 안 읽었음. OpenAI에서도 아무도 읽지 않았는데 내가 왜 읽어야 하나? 다른 수학자들이 AI가 쏟아낸 저질 수학을 다루듯, 나도 그것을 다시 생성기에 넣고 챗봇으로 핵심 사실을 추출했음. 의인화해서 말하자면 ChatGPT에 자기 출력물을 어떻게 생각하는지 물어본 것임. 이제 수학 연구를 이렇게 하고 있으니, 참 대단한 세상임.”

“컴퓨터 과학 이론은 컴퓨터에 관심 없는 수학이 됐다”는 문장이 이 글을 잘 요약함. 내게는 불평에 가까운 글이며, 핵심 불만은 정확한 복소수 곱셈을 가정하는 은하적 알고리즘이라는 데 있어 보임.
하지만 컴퓨터 과학 이론은 애초에 Alan Turing의 수학적 모형에서 출발함. 무한 테이프를 제쳐두더라도, 튜링 기계의 구조는 실용 목적으로 만든 어떤 컴퓨터와도 크게 다름.
직접적인 응용이 없는 수학을 싫어할 수는 있지만, 그래도 정당한 수학 연구임. 이번 AI 발표를 비난하는 손쉬운 구실로 삼지 말고, 논증의 오류나 출처 누락 등 논문 자체의 실질적인 결함을 찾아 보여주길 바람.

복소수의 크기가 n에 대해 초다항적으로 증가한다면, 빅오 분석 자체가 무효가 되는 것 아닌가? OpenAI의 n log n 미만 시간 “증명”이 뭔가를 숨기는 식으로 편법을 썼을 거라 의심했는데, 바로 이 부분 같음.

FFT 쪽은 모르겠지만, 적어도 O(n log n) 미만 곱셈 결과는 테이프 수가 고정된 다중 테이프 튜링 기계 모형을 사용함. 오히려 실제 임의 접근 메모리보다 제약이 큰 모형임.
물론 기존 O(n log n) 알고리즘처럼 여전히 은하적 알고리즘이지만, 분명 의미 있는 무언가가 있어 보임.

입력 수의 비트 길이에 대해서는 선형이면서 크기에 대해서는 지수적일 수 있음. 복잡도에서는 흔한 일이며, 초록에서도 “크기 n”이 아니라 “길이 n”이라고 명시한 것으로 기억함.