Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs

이 논문은 수십 년간 못 깨졌던 3SUM과 최단경로(APSP) 문제의 교과서 알고리즘을 처음으로 다항식만큼 빠르게 개선했다.

이 논문은 한마디로 3SUM을 O(n^1.9992), APSP를 O(n^2.9995)에 푸는 새 알고리즘이다. 핵심은 얇은 행렬곱(일부 칸만 곱하는 계산)을 빠르게 하는 새 기법이다. 이 하나의 기술이 여러 문제로 환원되어 3SUM·APSP·Exact Triangle 등 오래된 난제의 복잡도 가설을 한꺼번에 무너뜨렸다. 특히 알고리즘을 처음 발견한 주체가 AI 모델 Claude였고, Lean 4 증명 보조기로 검증까지 마쳤다는 점이 의미 있다.

핵심 요약

• 3SUM을 50년 만에 처음으로 다항식만큼 빠르게 풀어, O(n^2)을 O(n^1.9992)로 줄였다.
• 하나의 얇은 행렬곱 알고리즘으로 APSP, Exact Triangle 등 수많은 문제가 동시에 빨라지는 구조다.
• AI 모델(Claude)이 핵심 알고리즘을 발견하고, 사람 저자들이 이해·확장했으며, Lean 4로 증명 검증까지 마쳤다.
• 세부 복잡도 이론(fine-grained complexity)의 가설 여러 개가 반증되어, 하한 증명 연구에 큰 영향을 준다.

논문 링크

외부 연구를 정리한 자료입니다. HDATF가 발표한 논문이나 제품 성능을 측정한 결과는 아닙니다.