정수 곱셈의 O(n log n) 한계가 무너졌다, 수학자도 AI도 놀란 결과
The recently proposed o(n log n) integer multiplication algorithm [pdf]
UNSW의 David Harvey가 최근 제안된 o(n log n) 정수 곱셈 알고리즘을 검토한 노트를 공개했다. 지난 2021년 자신과 van der Hoeven이 세운 O(n log n) 기록을 뛰어넘는 주장으로, 지수 ε가 2^-182처럼 극히 작아도 기존 개선 폭보다 기하급수적으로 크다고 강조한다. 그는 논문을 직접 읽지 못하고 Claude Fable 5.1의 설명에 의존해 결론에 이르렀으며, LLM이 몇 분 만에 논문 전체를 이해하는 속도에 경악한다. 결과는 그럴듯하지만 Lean 형식화가 나오면 신뢰가 크게 높아질 것이라고 본다.
인간과 LLM 사이의 이 '사고 속도' 격차는 표현하기 어려울 정도로 불안하게 만든다.
HN 토론
251- jdb1729
> o(n log n) 결과에 대한 형식화된 증명이 있으면 좋을 것 같습니다. 예를 들어 Lean으로요. 제가 알기로는 아직 존재하지 않습니다.
이 결과는 @platypii와 제가 (Mathlib의 TM2 머신에서) Lean으로 완전히 형식화했습니다. 지수는 계속 개선 중입니다(현재 1-2^-14.38): https://github.com/platypii/integer-mult-bounds-lean
기여는 언제나 환영합니다!
- Kapura
> 논문을 실제로 읽지는 않았습니다. 사실 밀접하게 관련된 세 편의 논문 [TC26a], [TC26b], [TC26c]가 있는데, 어느 것도 읽지 않았습니다. 읽으려고 했지만 곧 포기했습니다. 그 수학 덤프는 설명이 충실해 보이지 않습니다. 대신 Fable에게 [TC26a]를 설명해 달라고 했습니다. Fable은 논증을 이해하는 것 같고, 맞다고 생각합니다.
이건 건강한 상황 같지 않네요.
- kenferry
> 이 상황에서 제가 강조하고 싶은 또 다른 측면이 있습니다. 2주 동안 아주 열심히 노력한 끝에, 저는 [TC26a]의 극히 일부만 이해할 수 있었습니다. Fable에게 논문에 대해 물으면, 심지어 새로운 컨텍스트에서 시작해도 단 몇 분 만에 전체를 읽고 이해하는 것처럼 보입니다. 일부 독자들이 제 의인화된 용어에 불편해할 수 있다는 것을 압니다. 하지만 저는 '이해한다'가 정확하다고 믿습니다. LLM이 논문에 관한 온갖 질문, 아주 까다로운 기술적 세부 사항에 관한 질문까지도 정확하고 명료하게 답할 수 있는 것처럼 보이기 때문입니다. 그것이 바로 제가 인간 동료가 무언가를 '이해했다'고 판단하는 방식입니다. 인간과 LLM의 '사고 속도' 사이의 이 간극은 말할 것도 없이 불편합니다.
이건 대단히 이상합니다. 제가 이 시스템들을 경험한 것과 전혀 맞지 않기 때문입니다. 네, 일반적으로 자신감 있게 '들리기는' 합니다. 하지만 (예를 들어) 제가 이해하기 어려운 코드는 보통 기계도 이해하기 어려워하고, 저보다 지치지 않는 것은 맞지만 더 똑똑한 것은 아닙니다.
이 수학자는 Fable이 이해하는지 아닌지를 평가하기에 아주 좋은 위치에 있습니다. 하지만 이건 이상하고 제 경험과 상반됩니다.
- jdb1729
> 새로운 결과가 고정된 유한체 위에서의 다항식 곱셈, 예를 들어 F2[x]에서의 곱셈에 대한 새로운 복잡도 한계를 직접적으로 함의하지는 않습니다. 이 문제의 최신 기술은 차수 n인 다항식을 O(n log n 4^log*(n)) 시간에 곱하는 알고리즘입니다 [HvdH19].
@platypii와 저는 소수 차수 유한체 위의 DFT에 대해 동일한 개선을 Lean으로 증명했습니다(합성곱 정리를 통해 다항식 곱셈을 얻음): https://github.com/platypii/integer-mult-bounds-lean/blob/ma...
- flebron
이 경우 제목이 "O(n log n)"이라고 되어 있지만, 중요한 부분은 이것이 "o(n log n)"이라는 점입니다. 단순한 "O(n log n)"이 아니라요. 전자는 후자의 진부분집합입니다. 우리는 이미 FFT를 통해 두 n비트 정수를 O(n log n) 시간에 곱하는 방법을 알고 있었습니다.
- CH-Abhinav
여기 새로 왔는데 이게 일반적으로 어떻게 도움이 되나요? 대부분의 경우 시간 복잡도가 더 낮음에도 불구하고 Strassen보다 GEMM을 사용합니다. 그냥 아무거나 물어보세요 :)
- kleiba2
흥미롭네요. AI는 분명히 인간을 위한 논문을 쓰지 않는 것 같습니다. 전문가들조차 이해하기 어려워하니까요. 하지만 다른 AI들은 이해합니다. 그래서 AI는 기본적으로 다른 AI를 위해 논문을 쓰는 겁니다.
- yaoke259
멋진 글과 소개였습니다, 같은 시드니 사람으로서 푹 빠져서 읽었어요! 수학 천재가 아닌 저로서는 기술적인 세부 사항은 머리를 스쳐 지나갔지만, 업계 사람들에게 깊이 공감할 수 있게 해주는 문장이 매우 계몽적이었습니다. 수학 덤프가 얼마나 큰 사건이었는지, 그리고 그것이 이 분야를 얼마나 뒤흔들었는지 전혀 몰랐습니다. 우리 모두 이 '즉시 사용 가능한 지능'이라는 것을 함께 알아가고 있는 것 같네요.