3SUM과 APSP의 지배적 가설이 깨졌다

Subquadratic 3SUM and Subcubic APSP

3SUM과 APSP에 대한 기존의 지수적 장벽을 처음으로 다항식 수준에서 개선한 연구가 나왔다. 3SUM은 O(n^1.9992)에, APSP는 O(n^2.9995)에 결정론적으로 해결 가능하다. 이는 3SUM 및 APSP 가설을 반증하며, Exact Triangle 가설과 Zero-Weight k-Clique 가설, 그리고 van den Brand, Nanongkai, Saranurak의 세 가지 직사각형 힌트 Online Matrix-Vector 추측도 함께 반증한다. 핵심은 희소 비대칭 삼분 그래프의 삼각형 문제를 진정한 서브쿼드라틱 시간에 푸는 새로운 알고리즘이다.