AI 요약
Josh Alman과 Virginia Vassilevska Williams가 3SUM과 모든 쌍 최단 경로(APSP) 문제에 대해 교과서적 알고리즘을 처음으로 다항식 수준에서 개선하는 연구를 발표했다. 이들은 3SUM을 O(n^1.9992) 시간에, APSP를 O(n^2.9995) 시간에 결정론적으로 해결하는 알고리즘을 제시하며 3SUM 및 APSP 가설을 반박했다. 이 결과는 얇은 행렬 곱셈을 위한 단일 새 알고리즘에서 비롯되었으며, Schönhage의 10회 곱셈 항등식에 기반한 Coppersmith의 직사각형 행렬 곱셈 변형을 수정해 개발됐다. 이는 Exact Triangle 가설, Zero-Weight k-Clique 가설, 세 가지 직사각형 힌트 온라인 행렬-벡터 추측 등도 반박한다.
핵심 포인트
- 3SUM을 O(n^1.9992) 시간에, APSP를 O(n^2.9995) 시간에 결정론적으로 해결하는 최초의 다항식 개선 알고리즘
- 3SUM 및 APSP 가설을 반박하고, Exact Triangle·Zero-Weight k-Clique·온라인 행렬-벡터 추측도 반박
- D ≤ N^(1/18)인 얇은 행렬 곱셈 알고리즘으로, W 위치의 항목을 O(N²/D^0.063) 연산으로 계산
- 논문은 76페이지 분량으로 arXiv:2610.06783에 2026년 10월 5일 제출
향후 전망
- 이 알고리즘으로 다양한 다른 문제들의 다항식 속도 향상이 가능해질 전망
- 그래프 알고리즘 분야에서 희소 비대칭 삼분 그래프의 All-Edges Sparse Triangle 문제 해결에 기여
출처:hackernews