최근 제안된 o(n log n) 정수 곱셈 알고리듬 [PDF]

새 알고리듬은 n비트 정수 곱셈을 O(n(log n)^(1−ε)) 비트 연산에 수행한다고 주장함. 기존 최선이자 최적이라고 널리 여겨졌던 O(n log n)보다 점근적으로 작은 복잡도임 2021년 O(n log n) 알고리듬의 공동 개발자 David Harvey는 결과가 맞을 가능성이 있다고 잠정적으로 판단함. 다만 관련 논문 세 편을 끝까지 읽거나 증명을 상세히 검증하지 않았으며, Claude Fable 5.1과의 논의로 일부 논리를 이해한 상태임 핵심 아이디어는 여러 독립적인 푸리에 변환을 함께 처리할 때 버터플라이 연산 호출을 평균적으로 줄이고, 작은 절감을 텐서 거듭제곱의 재귀 구조로 증폭하는 것임 최초 제안의 ε는 2^−182로 극히 작지만, (log n)^ε라는 개선 폭은 이전 정수 곱셈 알고리듬들의 점근적 개선보다 훨씬 큼. 다만 단일 변환을 직접 단축하는 방식이 아니라 여러 입력을 묶는 구조가 필요함 결과가 맞다면 Li–Li 네트워크 코딩 추측을 반증하는 등의 파급 효과가 있음. 그러나 유한체 다항식 곱셈에 곧바로 같은 개선이 적용되는 것은 아니며, 형식화된 증명도 아직 확인되지 않음 제안된 복잡도와 검증 상태 익명의 미국 기술 기업이 GitHub에 공개한 다수의 수학 원고 중 [TC26a] 는 n비트 정수 곱셈을 다중 테이프 튜링 기계 모델과 불리언 회로 모델 모두에서 o(n log n) 비트 연산에 수행한다고 주장함 구체적인 상한은 어떤 작은 양의 상수 ε에 대한 O(n(log n)^(1−ε))임 기존 O(n log n)이 최적이라는 통념과 달리, 로그 항의 지수를 1 아래로 낮추는 결과임 Harvey의 판단은 가능성에 대한 잠정 평가이지 증명 검증이 아님 밀접하게 연관된 [TC26a], [TC26b], [TC26c] 모두 읽기를 시도했지만 중단했으며, 주로 Fable에 [TC26a]를 설명해 달라고 요청함 반복적인 질문으로 논증의 일부를 이해했고 O(n(log n)^α)라는 상한의 형태가 타당할 수 있다고 보지만, 이해하지 못한 부분과 확인하지 않은 세부 사항이 많음 Fable은 논증을 이해하고 옳다고 판단하는 듯했지만, 다른 최첨단 LLM들도 같은 판단을 했으리라는 기대는 직접 확인한 결과가 아님 Lean 등의 형식화된 증명은 아직 존재하지 않는 것으로 파악함 현재 기술로 가능할 듯하지만 쉬운 작업은 아니며, 결과가 맞다면 비교적 곧 나올 것으로 예상함 초기 정의와 주정리의 서술을 Lean...