10년 난제 풀었다, 정렬·최단경로 알고리즘 다항식 고속화
원제 Subquadratic 3SUM and Subcubic APSP
109 포인트댓글 49
Key Point
30년 이상 컴퓨터과학에서 풀리지 않던 기본 문제들의 다항식 고속화로, 정렬·최단경로 등 실제 알고리즘에 영향을 미칠 수 있는 이론적 진전이다.
핵심 요약
- Josh Alman과 Virginia Vassilevska Williams는 3SUM과 All-Pairs Shortest Paths(APSP) 문제를 처음으로 교과서 알고리즘보다 다항식만큼 빠르게 풀 수 있음을 증명했다.
- 3SUM은 n개의 정수를 O(n^1.9992) 시간에, APSP는 방향 그래프를 O(n^2.9995) 시간에 결정적으로 풀 수 있으며, 이는 각각 O(n²)과 O(n³)의 오래된 한계를 깼다.
- 이 결과는 3SUM과 APSP 추측(가설)뿐 아니라 실수 버전의 같은 문제들, Exact Triangle 추측, Zero-Weight k-Clique 추측 등 관련 문제 여러 개를 동시에 반박한다.
- 핵심은 N×D 행렬 X와 D×N 행렬 Y(D≤N^1/18)의 선택적 곱셈을 O(N^2/D^0.063) 연산으로 계산하는 알고리즘으로, Coppersmith의 직사각형 행렬 곱셈 알고리즘을 Schönhage의 십중곱 항등식을 바탕으로 수정했다.
- 그래프 관점에서 보면 이 알고리즘은 한 쪽 정점이 n^ε(ε<0.12)개인 희소 불균형 삼분 그래프에서 삼각형 탐지를 완전히 이차식 미만 시간에 푼다.
- Exact Triangle과 3SUM, APSP가 이 삼각형 문제로 귀결되는 기존 축약을 이용하면, 이들 고전적 문제들도 새 알고리즘으로 더 빠르게 해결된다.
- 저자들은 또한 미리 알려지지 않은 개별 행렬 곱 항목에 응답하는 자료구조 버전도 제시했다.
- 총 76쪽의 논문은 2026년 10월 5일 arXiv에 제출되었다.