알고리즘 이론에서 오랫동안 '넘을 수 없는 벽'처럼 여겨지던 두 문제, 3SUM과 모든 쌍 최단 경로(APSP)에 대해 교과서 알고리즘을 처음으로 다항식 수준으로 앞지른 결과가 arXiv에 공개됐다. 이 논문은 n개의 정수(다항식 크기)에 대한 3SUM을 O(n^1.9992) 시간에, 정수 가중치가 다항식 범위로 제한된 유향 그래프의 APSP를 O(n^2.9995) 시간에 결정론적으로 푸는 방법을 제시한다. 수치만 보면 2 또는 3에서 소수점 아래 네 자리를 깎아낸 미미한 개선처럼 보이지만, 이론 전산학의 맥락에서는 '넘지 못할 선'을 넘었다는 점 자체가 핵심이다.
왜 소수점 네 자리가 중요한가
3SUM은 '세 수를 더해 0이 되는 조합이 있는가'를 묻는 단순한 문제이고, APSP는 그래프의 모든 정점 쌍 사이 최단 거리를 구하는 고전적 문제다. 두 문제 모두 수십 년간 각각 n²과 n³에 매우 가까운 시간이 사실상 최선이라고 믿어져 왔다. 이 믿음은 단순한 경험칙이 아니라 'fine-grained(세밀) 복잡도' 이론의 토대가 되는 가설로 자리 잡았다. 즉 3SUM이나 APSP를 진짜로(truly) 더 빠르게 풀 수 없다는 전제 위에, 수많은 다른 문제의 하한이 조건부로 증명되어 왔다. 이번 결과가 두 가설을 모두 반증(refute)한다고 주장하는 이유가 여기에 있다.
파급 범위는 두 문제에 그치지 않는다. 알려진 환원(reduction)을 통해 저자들은 실수값 버전의 3SUM·APSP 가설, Exact Triangle 가설, Zero-Weight k-Clique 가설들, 그리고 van den Brand, Nanongkai, Saranurak이 제시한 세 가지 직사각형 힌트 온라인 행렬-벡터(Online Matrix-Vector) 추측까지 반증한다고 밝혔다. 이들 가설은 서로 환원으로 얽혀 있는 하나의 큰 생태계이기 때문에, 그 중심 축이 흔들리면 그 위에 세워진 조건부 하한들의 의미도 함께 재검토 대상이 된다. 논문은 이 밖에도 여러 문제에 대해 다항식 수준의 속도 향상을 제공한다고 덧붙인다.
하나의 알고리즘에서 모든 것이 나온다
흥미로운 점은 이 모든 결과가 '얇은 행렬 곱(thin matrix product)'을 위한 단 하나의 새 알고리즘에서 파생된다는 것이다. 구체적으로 N×D 정수 행렬 X와 D×N 정수 행렬 Y가 있고 D가 N^(1/18) 이하로 매우 작을 때, 전체 곱 XY를 다 구하는 대신 미리 지정된 최대 N²/√D개의 위치 집합 W에 속한 항목들만 계산한다. 이 계산을 O(N²/D^0.063) 연산으로 해내는데, 이는 XY 전체를 적어 내는 데 드는 시간은 물론이고 N²/√D개의 내적을 하나씩 따로 계산하는 시간보다도 다항식만큼 적다. '필요한 값만, 그러나 하나씩 계산하는 것보다 빠르게'라는 점이 이 알고리즘의 묘미다.
설계는 완전히 새로운 발명이라기보다 기존 도구의 영리한 재조립에 가깝다. 저자들은 Schönhage의 열 번 곱셈 항등식에서 출발한 Coppersmith의 직사각형 행렬 곱셈 알고리즘의 한 변형을 가져와, W에 속한 항목에 필요한 연산만 수행하도록 수정하고 그 연산 수가 적다는 것을 증명했다. 고속 행렬 곱셈이 실제 수치 계산이 아니라 조합적 문제의 구조를 공략하는 도구로 쓰인 셈이다.
희소 삼각형 문제라는 다리
이 알고리즘을 그래프 관점에서 해석하면 'All-Edges Sparse Triangle(모든 간선 희소 삼각형)' 문제를 특정 형태의 그래프에서 진짜 준이차(subquadratic) 시간에 푸는 것이 된다. 대상은 두 파트가 n개의 정점을 갖고 나머지 한 파트는 n^ε개(단 ε