10년 난제 풀었다, 정렬·최단경로 알고리즘 다항식 고속화
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 추측 등 관련 문제 여러 개를 동시에 반박한다.