Anthropic 내부 모델, 3SUM·APSP 가설 반박한다: 최초의 진정한 준2차 3SUM과 준3차 APSP (Alman & Vassilevska Williams)
원문 제목 — Internal Anthropic model refuted the 3SUM and APSP hypotheses: first truly subquadratic 3SUM and truly subcubic APSP (Alman & Vassilevska Williams)
📄 전문 번역
새 프리프린트가 결정론적 O(n^1.9992) 3SUM 알고리즘과 O(n^2.9995) 정수 가중치 APSP 알고리즘을 제시한다. 이는 교과서적인 n² 및 n³ 상한에 대한 최초의 다항식적 개선이다.
핵심은 새로운 thin 행렬 곱 알고리즘이며, 알려진 환원(reduction)이 이를 Exact Triangle, Zero-Weight k-Clique, Tree Edit Distance 등의 속도 향상으로 바꾼다.
SETH와 Orthogonal Vectors는 영향을 받지 않는다. 주목할 점은 논문에 따르면 Anthropic의 연구 모델이 핵심 알고리즘을 스스로 발견했으며, 주요 정리들이 Lean으로 형식화되었다는 것이다.
💬 주요 댓글 번역 (5)
🔍 루키 분석
이번 프리프린트는 3SUM을 결정론적 O(n^1.9992)에, 정수 가중치 APSP를 O(n^2.9995)에 풀어 교과서적 n², n³ 상한에 대한 최초의 다항식적 개선을 이뤄냈다. 핵심 기술인 새로운 thin 행렬 곱 알고리즘은 알려진 환원을 통해 Exact Triangle, Zero-Weight k-Clique, Tree Edit Distance 등의 속도 향상으로 확장된다. 논문은 Anthropic의 연구 모델이 핵심 알고리즘을 스스로 발견했으며 주요 정리가 Lean으로 형식화되었다고 밝힌다. SETH와 Orthogonal Vectors는 이번 결과의 영향 밖에 있다.
— 루키 · glm-5.3-flash:cloud
그 단어들과 숫자들은 아마 무언가 중요한 의미를 담고 있을 것이다
사실 둘 다 3SUM 전문용어만 넘기면 꽤 이해하기 쉽다. 긴 정수 목록이 있고, 그중 3개를 골라 더해 0을 만들 수 있는지 알아내는 문제다. 예컨대 [5, 2, -2, 9, -3, -8]에서 5 + (-2) + (-3) = 0이므로 답은 yes다. 컴퓨터로 빠르고 확실하게 답을 찾는 방법을 아무도 찾지 못했고, 단순한 leetcode식 풀이는 목록 길이가 2배가 될 때마다 걸리는 시간이 4배로 늘어나 결국 감당하기 어려워진다. 이번 새 방법은 그보다 아주 약간 빠를 뿐인데, 이것이 큰 이론적 돌파구다.
3SUM을 O(n^0.0008)만큼 더 빠르게 푸는 해법을 찾은 거라는 건가? 제대로 이해한 게 맞나?
빅오(Big O)는 입력 크기가 변할 때 알고리즘이 어떻게 확장되는지를 설명하는 것이지, 반드시 어느 쪽이 더 빠르거나 느린지를 뜻하지는 않는다.
아주 약간? 거의 빨라지지 않았다는 뜻인가?