💻 컴퓨터 과학

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

이 논문은 로프시디드 그래프(lopsided graphs)에서 행렬 곱의 희소 엔트리(sparse entries)를 계산하기 위한 새로운 알고리즘을 도입함으로써 3SUM 및 모든 쌍 최단 경로(APSP)에 대한 교과서적 알고리즘을 다항식 수준으로 개선한 첫 사례를 제시하며, 이는 3SUM 및 APSP 가설을 반박하고 수많은 관련 문제들에 대한 속도 향상을 가져온다.

원저자: Josh Alman, Virginia Vassilevska Williams

게시일 2026-10-06

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Josh Alman, Virginia Vassilevska Williams

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

컴퓨터 과학의 광활한 풍경 속에는 수십 년 동안 개선되지 않은 채 남아, 우리가 정보를 더 빠르게 처리하는 능력을 가로막는 과속 방지턱 역할을 해온 문제들이 존재합니다. 가장 유명한 두 가지는 '세 수 합(three-sum)' 문제와 '모든 쌍 최단 경로(all-pairs shortest paths)' 문제입니다. 첫 번째 문제는 단순한 질문을 던집니다: 숫자 목록이 주어졌을 때, 합이 0이 되는 세 숫자를 찾을 수 있는가? 오랫동안 이 문제를 큰 숫자 목록에 대해 해결하는 최선의 방법은 목록 크기의 제곱에 비례하는 시간이 걸렸습니다. 두 번째 문제는 도로 네트워크 내의 모든 도시 쌍 사이의 최단 거리를 구하는 것입니다. 이를 위한 최선의 방법은 항상 도시 수의 세제곱에 비례하는 시간이 걸려 왔습니다. 수년 동안 컴퓨터 과학자들은 이러한 한계가 깨뜨릴 수 없는 것이라고 믿었으며, 어떤 알고리즘도 교과서적인 방법보다 유의미하게 더 빠를 수 없음을 시사하는 '가설'이라는 규칙들을 형성했습니다. 이 문제들은 단순히 추상적인 퍼즐이 아닙니다. 이들은 지도 소프트웨어부터 복잡한 데이터의 패턴 탐지에 이르기까지 모든 것의 기초가 되며, 따라서 이러한 속도 제한을 깨는 방법을 찾는 것은 계산 방식에 있어 기념비적인 변화가 될 것입니다.

컬럼비아 대학교와 MIT의 연구진은 앤스로픽(Anthropic)이 개발한 인공지능 모델과 협력하여, 오랫동안 유지되어 온 이러한 믿음을 깨뜨렸습니다. 그들은 이 문제들을 해결하는 진정으로 더 빠른 새로운 방법을 발견했습니다. 세 수 합 문제의 경우, 입력 크기의 제곱에 비례하는 시간이 걸리는 대신, 그들의 새로운 방법은 제곱보다 약간 적은 시간 안에 문제를 해결합니다. 마찬가지로, 최단 경로 문제의 경우, 필요한 시간을 도시 수의 세제곱보다 약간 적게 줄였습니다. 이것은 사소한 수정이나 특수한 경우에만 작동하는 트릭이 아닙니다. 이는 광범위한 입력에 적용되는 근본적인 개선입니다. 이 문제들을 더 빠르게 해결할 수 있음을 증명함으로써, 연구진은 이들이 불가능하다고 주장했던 가설들을 효과적으로 반박했습니다.

이 돌파구의 비결은 데이터를 표현하기 위해 사용되는 숫자 격자인 행렬(matrix)을 곱하는 기발하고 새로운 접근 방식에 있습니다. 연구진은 정사각형이 아니라 매우 가늘고 긴 형태의 행렬을 사용하는 특정 유형의 행렬 곱셈에 집중했습니다. 그들은 최종 결과의 모든 숫자를 계산하는 대신, 단 몇 개의 특정 지점에 대한 답만 알면 된다면 엄청난 양의 작업을 건너뛸 수 있다는 사실을 깨달았습니다. 그들은 아무도 요구하지 않은 답을 만들어내는 계산을 무시하는 고도로 효율적인 필터처럼 작동하는 알고리즘을 설계했습니다. 이 기술은 숫자를 결합하는 규칙인 오래된 수학적 항등식을, 중요한 특정 정보에만 작동하도록 수정함으로써 구축되었습니다.

이 발견의 힘은 서로 다른 컴퓨터 문제들이 어떻게 연결되어 있는지에서 나옵니다. 미세 정밀도 복잡도(fine-grained complexity)의 세계에서 연구자들은 한 문제를 해결하는 것이 다른 문제를 해결하는 데 어떻게 도움이 되는지를 매핑하는 데 수년을 보냈습니다. 그들은 만약 '세 수 합' 문제를 더 빠르게 해결할 수 있다면, '최단 경로' 문제 또한 더 빠르게 해결할 수 있다는 것을 발견했습니다. 그 반대의 경우도 마찬가지입니다. 새로운 알고리즘은 마스터 키 역할을 합니다. 특정 행렬 곱셈 문제를 해결함으로써, 연구진은 이전까지 기존 속도에 갇혀 있다고 여겨졌던 수십 가지의 다른 문제들에 대한 더 빠른 해결책을 열었습니다. 여기에는 네트워크에서의 삼각형 찾기, 데이터의 특정 패턴 확인, 그리고 다양한 유형의 탐색 및 정렬 작업 최적화 등이 포함됩니다.

연구진은 단순히 이론적인 가능성을 제시한 것이 아니라, 매번 작동하는 구체적이고 결정론적인 방법을 제공했습니다. 또한 그들의 접근 방식이 정수뿐만 아니라 대부분의 실제 과학 계산에 사용되는 실수(real numbers)를 다룰 때도 작동함을 보여주었습니다. 연구진은 강력한 AI 도구를 사용하여 수학적 증명을 검증함으로써, 속도 향상의 논리가 타당함을 확인했습니다. 인간 연구자와 인공지능의 이러한 협업은 기계가 인간이 놓칠 수 있는 깊은 수학적 진리를 밝혀낼 수 있는 새로운 과학적 발견의 시대를 강조합니다.

이 연구의 영향은 세 수 합과 최단 경로라는 특정 문제를 훨씬 넘어 확장됩니다. 이는 일부 계산적 한계가 절대적이라는 생각에 도전합니다. 수십 년 동안 학계는 특정 문제들을 해결하는 데 특정한 양의 시간이 필요하며, 더 빨라지려는 시도는 헛된 일이라고 받아들여 왔습니다. 이 논문은 이러한 한계가 벽이 아니라, 올바른 관점을 통해 높일 수 있는 천장임을 보여줍니다. 현재 이 알고리즘들은 거대한 숨겨진 상수(hidden constants)들 때문에 일상적인 소프트웨어에서 사용하기에는 너무 복잡하지만, 그것이 존재한다는 증명은 컴퓨터 과학의 이론적 토대를 바꿉니다. 이는 미래의 연구자들이 이 방법들을 정교화하여, 결과적으로 거대한 데이터 세트를 그 어느 때보다 훨씬 더 효율적으로 처리할 수 있는 실용적인 도구로 발전시킬 수 있는 문을 열어줍니다. 연구진은 가장 완고한 문제조차도 새로운 사고를 통해 굴복할 수 있음을 보여주었으며, 계산 가능한 것의 경계는 언제나 테스트할 가치가 있다는 것을 증명했습니다.

기술 요약: 희소한 로프사이드(Lopsided) 그래프에서의 삼각형을 통한 진정한 준이차 및 진정한 준삼차 3SUM 및 APSP

1. 문제 정의

본 논문은 수십 년 동안 상당한 개선이 이루어지지 않았던 미세 조정 복잡도 이론(fine-grained complexity theory)의 두 가지 근본적인 문제를 다룹니다:

3SUM: $n$ 개의 다항식 크기 정수가 주어졌을 때, 세 수의 합이 0이 되는지 결정합니다. 표준 알고리즘은 $O(n^2)$ 시간에 실행되며, 3SUM 가설은 어떤 알고리즘도 이를 $O(n^{2-\epsilon})$ 시간(단, $\epsilon > 0$ ) 내에 해결할 수 없다고 가정합니다.
모든 쌍 최단 경로 (APSP): $n$ 개의 정점을 가진 유향 그래프와 다항식으로 제한된 정수 가중치가 주어졌을 때, 모든 쌍 사이의 최단 경로를 계산합니다. 표준 알고리즘(Floyd-Warshall, Johnson)은 $O(n^3)$ 시간에 실행됩니다. APSP 가설은 어떤 알고리즘도 이를 $O(n^{3-\epsilon})$ 시간 내에 해결할 수 없다고 가정합니다.

또한 본 논문은 정확한 삼각형(Exact Triangle) 문제(삼분 그래프에서 총 간선 가중치가 0인 삼각형을 찾는 문제)와 유향 비가중치 APSP(Directed Unweighted APSP) 문제, 그리고 이들과 미세 조정 환원(fine-grained reductions)을 통해 동등한 다양한 문제들(예: $(\min, +)$ -곱, 트리 편집 거리, Zero-Weight $k$ -Clique)을 목표로 합니다.

2. 방법론

핵심 기여는 두 "얇은(thin)" 행렬의 곱에서 지정된 희소한 엔트리 집합을 계산하는 새로운 알고리즘입니다.

2.1 얇은 행렬 곱 알고리즘 (Thin Matrix Product Algorithm)

저자들은 다음 조건을 만족하는 두 "얇은" 행렬의 곱 $XY$ 에서 엔트리 집합 $W$ 를 계산하는 결정론적 알고리즘을 개발했습니다:

$X$ 는 $N \times D$ 정수 행렬입니다.
$Y$ 는 $D \times N$ 정수 행렬입니다.
$D \le N^{1/18}$ 입니다 (행렬이 "얇음").
$W$ 는 최대 $N^2/\sqrt{D}$ 개의 위치를 가진 집합입니다.

핵심 기술 혁신:
이 알고리즘은 Schönhage의 10-곱셈 항등식을 기반으로 하는 Coppersmith의 직사각형 행렬 곱셈 알고리즘을 수정합니다.

재귀적 구조: 알고리즘은 Schönhage의 항등식을 재귀적으로 적용합니다. 모든 $N^2$ 엔트리를 계산하는 표준 행렬 곱셈과 달리, 이 알고리즘은 재귀 트리를 가지치기(pruning)합니다.
가지치기 전략: 알고-리즘은 $W$ 를 계산하는 데 필요한 재귀 트리의 "리프(leaf)" 노드만을 방문합니다.
인코딩 공유: "인코딩" 단계(입력 블록의 선형 결합)는 특정 출력 엔트리가 아닌 입력 행렬에만 의존합니다. 알고리즘은 각 입력 블록에 대해 인코딩을 한 번만 계산하고 이를 모든 필요한 계산에 공유합니다.
리프 분석: 저자들은 재귀 트리의 리프 "차수(order)"를 분석합니다. 단일 출력 엔트리는 많은 리프를 필요로 하지만, 대부분의 리프는 많은 출력 엔트리 간에 공유된다는 것을 증명합니다. 서로 다른 차수의 리프 수를 정밀하게 조절함으로써, 희소 집합 $W$ 를 위해 필요한 총 리프 수가 전체 곱을 계산하거나 개별적으로 엔트리를 계산하는 비용보다 현저히 작음을 보여줍니다.

복잡도:
이 알고리즘은 $O(N^2 / D^{0.063})$ 시간(로그 인자 포함) 내에 $W$ 의 엔트리들을 계산하며, 이는 전체 곱을 작성하는 데 걸리는 $O(N^2)$ 시간이나 내적으로서 엔트리를 개별적으로 계산하는 데 걸리는 $O(N^2 \sqrt{D})$ 시간보다 다항식적으로 빠릅니다.

2.2 그래프 문제로의 환원

이 행렬 알고리즘은 로프사이드 올-에지 스파스 트라이앵글(Lopsided All-Edges Sparse Triangle) 문제에 적용됩니다. 이 문제에서는 삼분 그래프(부분 집합 $A, B$ 의 크기는 $n$ , 중간 부분 $M$ 의 크기는 $D \ll n$ )의 간선 $(a, b)$ 집합이 삼각형에 포함되는지 여부를 찾습니다.

행렬 해석: 이는 그래프의 인접 행렬들의 곱에서 해당하는 위치의 엔트리를 계산하는 것과 같습니다.
결정론적 환원: 본 논문은 Exact Triangle(일반 그래프 상의)에서 Lopsided All-Edges Sparse Triangle로의 결정론적 환원을 제공합니다. 이는 오탐(false positive)을 최소화하기 위해 결정론적으로 선택된 소수(prime)로 간선 가중치를 해싱한 후 증거(witness)를 탐색하는 과정을 포함합니다.
환원 체인: 알려진 미세 조정 환원들은 3SUM 및 APSP를 Exact Triangle로 연결합니다. 이러한 환원들을 새로운 Lopsided All-Edges Sparse Triangle 알고리즘과 결합함으로써, 저자들은 원래 문제들에 대한 더 빠른 알고리즘을 도출합니다.

3. 주요 기여 및 결과

3.1 가설의 반증

본 논문은 3SUM 및 APSP의 교과서적인 알고리즘에 대해 최초의 다항식 개선을 제시함으로써, 미세 조정 복잡도 이론의 3SUM 및 APSP 가설을 반증합니다.

3SUM: 다항식 크기의 정수에 대해 $O(n^{1.9992})$ 시간에 결정론적으로 해결되었습니다.
APSP: 다항식으로 제한된 정수 가중치를 가진 유향 그래프에 대해 $O(n^{2.9995})$ 시간에 결정론적으로 해결되었습니다.
Exact Triangle: 결정론적으로 $O(n^{2.9983})$ 시간에 해결되었습니다.
Directed Unweighted APSP: $O(n^{2+\mu-\epsilon})$ 시간( $\mu < 0.5275}$ )에 결정론적으로 해결되어, Zwick의 알고리즘이 최적이라는 가설을 반증했습니다. 이는 단순히 더 빠른 직사각형 행렬 곱셈 경계로부터 유도된 것이 아닌 첫 번째 개선 사례입니다.

3.2 실수 버전 (Real-Valued Variants)

비교, 덧셈, 뺄셈만을 사용하는 Chan, Vassilevska Williams, Xu의 환원을 사용하여, 저자들은 실수 버전 문제들에 대한 Las Vegas 알고리즘(오류가 없는 확률적 알고리즘)을 제공합니다:

Real 3SUM: 기대 시간 $O(n^{1.998})$ .
Real APSP: 기대 시간 $O(n^{2.998})$ .

3.3 광범위한 알고리즘적 영향

알려진 환원을 통해, 새로운 기법은 다음과 같은 다양한 문제들에 대한 다항식 속도 향상을 가져옵니다:

행렬의 $(\min, +)$ -곱.
트리 편집 거리 (Tree Edit Distance) (다항식으로 제한된 정수 비용의 경우).
임의의 상수 $k \ge 3$ 에 대한 Zero-Weight, Min-Weight, Max-Weight $k$ -Clique.
Online Matrix-Vector (OMV) 추측: 얇은 힌트(thin hints)를 제공하는 데이터 구조를 통해 "힌트가 주어진" OMV 추측의 변형들을 반증합니다. 이 데이터 구조는 행렬을 $O(N^2/D^{0.063})$ 시간에 전처리하고 단일 엔트리 쿼리에 대해 내부 차원 대비 부선형(sub-linear) 시간에 응답합니다.
Knapsack 및 Approximate Subset Sum: Unbounded Knapsack에 대한 최초의 진정한 준이차 알고리즘 및 Subset Sum에 대한 근사 스킴을 제공합니다.

3.4 데이터 구조 버전

저자들은 행렬 알고리즘을 데이터 구조로 확장합니다. $X$ 와 $Y$ 를 $O(N^2/D^{0.063})$ 시간에 전처리한 후, 임의의 단일 엔트리 $(XY)[I, J]$ 를 $O(D^{0.437})$ 시간에 계산할 수 있습니다. 이를 통해 타겟 엔트리를 미리 알 수 없는 문제들을 해결할 수 있습니다.

4. 의의 및 주장

저자들은 이 연구를 "미세 조정 복잡도의 큰 성공"으로 간주합니다.

알고리즘으로서의 환원: 본 논문은 미세 조정 환원이 주로 조건부 하드함을 추론하는 데 사용되었던 것과 달리, 그 자체로도 알고리즘임을 강조합니다. 하나의 새로운 기술(얇은 행렬 곱 알고리즘)이 서로 연결된 방대한 문제 네트워크를 동시에 가속화할 수 있습니다.
현상 유지에 대한 반박: 이 결과들은 3SUM 및 APSP의 "정체된" 실행 시간들이 근본적인 장벽이 아니라, 당시 가용했던 기술의 산물이었음을 입증합니다.
한계 및 열린 질문:
- 저자들은 본 기술이 CNF-SAT, Orthogonal Vectors, 또는 $k \ge 4$ 인 $k$ -SUM을 현재 개선하지 못한다는 점을 언급합니다. 이는 해당 문제들이 여기서 해결된 특정 희소 삼각형 인스턴스로 환원되지 않기 때문입니다.
- 알고리즘은 대수적이며 현재 숨겨진 상수(hidden constants)가 커서 즉각적인 실무 적용에는 비실용적입니다.
- 세 부분의 크기가 모두 $n$ 인 Balanced 형태의 All-Edges Sparse Triangle 문제는 이 기술로 해결되지 않았으며, 해당 경우의 $m^{4/3}$ 가설은 여전히 유효합니다.
- 논문은 더 나은 환원이나 정교한 대수적 항등식을 통해 더 나은 지수(exponent)를 찾을 가능성이 높다고 언급하며, 현재의 결과가 최적이라고 주장하지 않습니다.

5. 발견에 관한 방법론 노트

본 논문은 핵심 알고리즘이 Anthropic에서 개발한 AI 모델인 Claude에 의해 발견되었음을 명시적으로 밝힙니다. 저자들(Josh Alman 및 Virginia Vassilevska Williams)은 알고리즘을 이해하고, 단순화하며, 강화 및 확장하고, 그 결과를 도출하고 공식화하는 작업을 수행했습니다. 주요 결과는 Lean 4 증명 보조 도구를 사용하여 검증되었습니다. 저자들은 논문의 내용과 발표에 대해 모든 책임을 집니다.