OpenAI, 정수 곱셈의 n log n 장벽을 허물다
Integer multiplication below n log n
OpenAI가 공개한 수학 프리프린트 저장소에 정수 곱셈을 n log n 이하로 끌어내리는 연구가 포함됐다. 이는 수십 년간 굳건했던 이론적 하한을 깨는 결과로, 암호학과 알고리즘 전반에 파장이 예상된다. 같은 저장소에는 수백 편의 난제 해결 및 반례 논문이 함께 실려 학계의 주목을 받고 있다.
정수 곱셈을 n log n 이하로 끌어내리다.
HN 토론
63- TGower
우리는 nlogn에서 겨우 1/6129982163463555433433388108601236734474956488734408704만큼을 깎아냈다
- shmoil
n lg n ^ (1 - 2^{-182})에서 소리 내서 웃었다. 너무 웃기다.
- wk_end
이것에 대해 기계 검증된 증명이 딸려 있나?
우리는 회사에서 완전히 vibe-code 모드로 일하고 있어서, 프런티어 모델이 얼마나 강력할 수 있는지, 그리고 그걸 막으려고 엄청 애써도 얼마나 자주 자신 있게 미묘하게(혹은 그렇게 미묘하지도 않게) 틀린 걸 말할 수 있는지 둘 다 이해한다.
그래서 Lean 개발이나 광범위한 인간 검증이 없다면, 나는 좀 회의적이고, 심지어 이게 틀렸으면 하고 바라기까지 한다 — AI에 대한 내 그다지 긍정적이지 않은 감정 때문만이 아니라, 수학의 아름다움에 대한 내 성향 때문이다. n log n이 여기 있는 것보다 훨씬 더 낫다.
- MinimalAction
잘 모르는 사람을 위해 묻자면, 임계값보다 그렇게 많이 낮아 보이지도 않는데 왜 이게 흥미로운가?
- 12390asdjkas
이건 내가 최소 2^118000개 항목의 배열을 가질 때 완벽하다
진정으로 일반화되지 않는 한 제안된 곱셈 속도 향상에는 절대 관심 갖지 않을 것이다