요약
AI Claude가 찾은 알고리즘으로 3SUM과 APSP의 오랜 시간 하한 가설이 깨졌습니다.
조시 올먼과 버지니아 바실렙스카 윌리엄스가 arXiv에 올린 76쪽 논문입니다. 저자들은 앤트로픽의 AI 모델 Claude가 알고리즘을 처음 찾았고, 자신들은 이를 이해하고 다듬어 확장했다고 밝혔습니다.
왜 중요한가
- 두 가설은 세밀 복잡도 이론(문제마다 정확한 다항식 시간 한계를 따지는 분야)의 핵심 전제였습니다.
- 수십 년간 빨라지지 않은 여러 문제를 "3SUM만큼 어렵다"는 식으로 설명해 왔는데, 그 근거가 무너졌습니다.
- AI가 주요 복잡도 가설을 반박하는 알고리즘을 찾았고, 주요 결과는 Lean 4(증명을 기계로 검사하는 도구)로 검증됐습니다.
핵심 내용
- 3SUM(n개의 수 가운데 합이 0인 세 수가 있는지 판정하는 문제)을 O(n^1.9992) 시간에 풉니다.
- APSP(그래프의 모든 꼭짓점 쌍 사이 최단 거리를 구하는 문제)는 O(n^2.9995) 시간에 풉니다.
- 핵심 기법은 얇은 행렬 곱에서 필요한 칸만 골라 계산하는 새 알고리즘입니다.
- 기존 환원을 이용해 실숫값 버전, 정확한 삼각형 가설, 영 가중치 k-클리크 가설 등도 함께 반박했습니다.
- 다만 SETH(강한 지수 시간 가설)와 힌트 없는 OMv 가설은 영향을 받지 않는다고 밝혔습니다.
HN 반응
- 3SUM이 n²보다 빠를 수 없다고 다들 믿었기에 놀랍다는 반응이 많았고, 지수 1.9992에 실용적 의미가 있느냐는 물음도 나왔습니다.
- 행렬 곱셈 지수 개선처럼 후속 경쟁을 부를 것이라는 기대와, 이 가설에 기댄 조건부 하한 연구가 한꺼번에 무너졌다는 평가가 엇갈렸습니다.
저는 https://www.proofatlas.ai/open-problems/ 에서 LLM이 순위를 매긴 '수학에서 가장 중요한 미해결 문제 500선' 목록을 관리하고 있습니다. 이 문제는 159위였고, 244위인 "All-Pairs Shortest Paths in Truly Subcubic Time"도 함께 해결했습니다. Lean으로 형식화도 되어 있습니다.
그런데 놀라운 건, 최근 하루 이틀 사이에 LLM의 도움을 받은 해법이 줄줄이 나왔다는 겁니다. 95위 KLS(Kannan–Lovász–Simonovits) 추측은 세 저자가 따로따로 풀었는데, 모두 10월 1일에 나온 Song–Zhang의 핵심 판정 기준을 확장한 것입니다. 278위 Mumford–Shah 추측도 나왔고, 227위 SIC-POVM 존재에 관한 Zauner 추측도 모든 차원에서 풀렸다고 합니다. 이건 실이차체(real quadratic field)에 대한 힐베르트의 열두 번째 문제(36위)에서도 큰 진전을 주장하는 결과입니다.
오픈AI가 미해결 추측 100개에 대한 해법을 곧 공개할 거라는 얘기가 돌아서, 다들 선수를 빼앗기지 않으려고 서두르는 것 같습니다.
그 사이트에 해법이 나온 날짜 목록 같은 게 있나요? 아니면 풀린 문제는 목록에서 빼시나요?
네, 최근에 해결된 문제는 https://www.proofatlas.ai/open-problems/#resolved-problems 에서 보실 수 있습니다. 지금은 업데이트를 묶어서 하고 있는데, 곧 매일 하는 방식으로 바꿀 예정입니다.
지금은 arXiv에 올라온 해법 주장들의 수학적 내용을 LLM에게 검수시키고 있습니다. 정책을 바꿨는데도 arXiv는 여전히 아무 글이나 던져 놓는 곳이거든요. 검수해 보니 틀린 증명이 벌써 여섯 건 나왔고, 그 때문에 지금도 분명히 완전한 미해결이어야 할 문제들의 상태 표기가 꼬였습니다.
원하시는 건 감사의 글에 있는 버전입니다.
수학자였던 입장에서 말하자면, 이제 LLM을 수학에 쓰는 건 좀 질립니다. 되는 건 이미 다 알잖아요. 저는 이걸 '데이터 구축' 쪽에 쓰면 좋겠어요. 라이브러리, 이론, 실험 같은 걸 만드는 일이요. 하지만 LLM은 결국 연역 기계이고, 수학에는 초인적인 연역으로 따낼 수 있는 쉬운 열매가 많긴 하겠죠.
CS 쪽에서 보면 저는 좀 다르게 느껴져요. 특히 이 논문은 연구를 닫아 버리기보다 새로운 연구를 열어 줄 것 같고, 그래서 정말 흥분되고 AI를 쓸 만한 가치가 있는 일이라고 생각해요. 전혀 실용적이지 않은 알고리즘이긴 하지만(그게 뭐가 중요하겠어요), 지금까지 가설로 믿어 온 하한보다 나은 알고리즘이 있다는 걸 보였잖아요. 이런 결과는 그걸 더 개선하려는 경쟁(그리고 진짜 하한이 얼마인지 밝히려는 경쟁)을 불러일으키기 마련이에요. 저는 이 건에는 엄지를 들어 줄래요.
이 논문은 오히려 연구를 닫아 버리는 쪽이었습니다. 다만 재미있는 방식으로요.
조건부 하한에 관한 결과는 아주 많습니다. "이 문제가 이만큼 어렵다면, 저 문제도 저만큼 어려워야 한다"는 식이죠. 그런데 널리 쓰이던 가정이 틀렸다고 증명되면서 카드로 지은 집 전체가 무너졌습니다.
이제 그 연구 방향은 막다른 길이 된 것 같습니다. 세부 사항의 차이에 흔들리지 않는 조건부 하한을 증명하는 방법을 찾기 전까지는요. "이 문제가 본질적으로 이만큼 어렵다면, 저 문제도 본질적으로 저만큼 어려워야 한다" 같은 형태의 결과를 얻고 싶은 거죠. 조건부 하한이 첫 번째 문제에 n^2 시간이 필요하다는 가정에 의존하는데 누군가 O(n^1.9992) 시간 알고리즘을 내놓더라도, 조금 약해진 조건부 하한은 여전히 남을 테니까요.
그렇긴 한데, 제 생각에 TCS는 현실의 최적화와는 별 상관이 없어요. 현실의 최적화는 최소 컷 플로 같은 아주 단순한 아이디어로 만든 가장 쉬운 알고리즘을 쓰잖아요.
맞아요! 이게 직접 실용적인 결과로 이어질 가능성은 낮고, 앞으로 20년 안에도 어려울 거예요. 하지만 스토더스, 그리고 이어서 버지니아 윌리엄스가 내놓은 행렬 곱셈 개선과 느낌이 아주 비슷해요. 20년 동안 아무 진전이 없던 문제에서 그의 박사 논문과 그녀의 첫 논문이 나온 뒤로 그걸 발판 삼은 후속 연구가 열두 편 넘게 나왔거든요. 그중 실용적인 결과로 이어진 건 없지만, 솔직히 그게 무슨 상관이겠어요? 문제를 더 잘 이해하게 되는 건 좋은 일이고, 어쩌면 앞으로 100년 안에는 실제로도 개선으로 이어질지 몰라요. 아닐 수도 있고요. :)
좋네요. 제가 수학자 '였던' 이유가 그거예요 ㅋㅋ
가끔 수학 문제를 다루는 비수학자로서 이 말이 정말 이해가 안 가요. 수학자들은 AI가 열어 주는 새 지평이 왜 반갑지 않은 거죠? 수학의 세계를 더 많이, 더 쉽게 발견할 수 있게 되는 건데요?
스레드 첫 댓글(그리고 저를 포함한 소셜 미디어 사람들)만 보고 일반화하지는 않으시면 좋겠어요. 저는 많은 수학자가 굉장히 들떠 있다고 생각해요. 제 공동 연구자들도 대부분 그렇고, 저도 그렇고요.
이런 도구들과 함께 사회적 변화가 동시에 많이 일어나고 있고, 그게 다 좋은 쪽은 아니에요. 괴로워서 지르는 비명은 나머지 이야기에 비하면 상대적으로 목소리가 아주 크기도 하고요.
아직 학계에 있는 수학자들의 경우, 연구직(특히 정년직)을 둘러싼 경쟁이 이미 미친 수준이라서 AI가 그 경쟁을 더 악화시킨다고 느끼기 때문이 아닐까 싶습니다.
저는 모든 수학자를 대표하지 않고, 전생(?)에 못 풀었던 문제를 풀려고 LLM을 분명히 쓰고 있어요. 그래도 이제 LLM이 수학을 잘한다는 건 알게 됐잖아요.
저는 정리보다 더 낮은 전기요금, 더 싼 월세, 건강에 대한 더 나은 이해 같은 게 더 필요해요.
이 둘은 서로 배타적인 노력이 아니에요. 비꼬는 것 같아 미안하지만, 전기요금도 월세도 낮췄으면 하고 건강에 대한 이해도 높아졌으면 하는 사람들 중 상당수는 수학자라는 직업 자체를 비판할 거예요.
흥미로운 점은 이제 LLM이 수학을 할 수 있다는 사실이 아닙니다. 흥미로운 건 이런 문제들이 이제 별 어려움 없이 풀린다는 거죠.
LLM의 가치는 "와, 이런 것도 하네, 신기하다"가 아닙니다. 구경거리가 아니에요.
이 분야는 전체가 평판으로 돌아가는데, AI를 연구에 쓰는 건 평판에 좋지 않다고 보는 시각이 있기 때문입니다.
전체 제목은 "Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs"입니다. 이게 일반적인 3SUM을 준이차 시간에 푼다는 것과 같은 말인가요? 여기서 Sparse Lopsided Graph(희소하고 한쪽으로 치우친 그래프)가 얼마나 큰 역할을 하는 건가요?
3SUM을 "희소 그래프에서 삼각형 찾기" 인스턴스 하나를 푸는 문제로 바꿀 수 있는데, 3SUM에서 나오는 그래프는 한쪽으로 치우쳐 있다는 게 핵심입니다(즉, 세 부분으로 나뉜 그래프에서 한 부분이 나머지 둘보다 훨씬 작습니다). 저자들이 이런 인스턴스를 위한 효율적인 알고리즘을 찾았고, 그래서 3SUM에 대한 효율적인 알고리즘도 얻은 겁니다.
오, 그럼 진짜 대단하네요! 저는 조건을 붙인 한정어인 줄 알았는데 사실은 그게 풀이 수단이었군요(네, 제목이 헷갈리네요).
네, 저도 해석하기 까다로웠어요. 그런데 "Triangles in Sparse Lopsided Graphs"는 "Truly Subquadratic 3SUM and Truly Subcubic APSP"를 보이는 데 쓴 기법이라는 뜻이에요.
와, TCS 커뮤니티에 이 결과의 배경을 설명해 주실 분 계신가요? 대부분 이런 게 가능하다고 생각했을까요, 불가능하다고 생각했을까요, 아니면 아예 생각해 본 적이 없었을까요?
가능하다고 생각한 사람은 없었어요.
3SUM 어려움은 보통 n^2 이상이라고 여겨졌거든요.
정말 믿기 힘든 결과예요! (개인적으로는 나비에-스토크스보다 이게 더 의미 있고 더 놀랍게 느껴져요. 에이전트가 해냈다는 점이 아니라, 결과 자체가 엄청나게 놀랍다는 얘기예요!)
이 부분을 좀 더 자세히 설명해 주실 수 있나요? 3SUM 결과를 처음 봤을 때 "뻔한 O(n^3) 알고리즘이 있고, 꽤 쉬운 O(n^2) 알고리즘이 있다" 같은 설명이 붙어 있었습니다. 15초쯤 생각해서 이런 방법을 떠올렸습니다. 모든 수를 해시 테이블에 넣고(O(n)), 모든 수의 쌍을 훑으면서(O(n^2)) 그 합의 음수가 테이블에 있는지 확인하는 겁니다(O(1)). 위키백과를 확인해 보니 기본적으로 이게 단순한 버전이더군요(상수가 더 작고 저장 공간이 더 적은 알고리즘도 있긴 하지만요).
그런데 제가 15초 만에 떠올린 알고리즘이(저는 이쪽에 별로 능숙하지도 않은데) 최적이라니 이상합니다. 이게 더 나아질 수 없다는 것(혹은 없었다는 것)이 오히려 더 놀랍습니다. 그러니 뭔가 이야기에 더 있는 게 틀림없습니다.
3SUM은 세밀한 복잡도(fine-grained complexity)의 핵심 추측 중 하나이고(였고?), 주로 다른 문제의 하한을 이끌어 내는 데 쓰였습니다. 그래서 대부분은 준이차 알고리즘이 가능하다고 보지 않았습니다. APSP도 마찬가지고요.
그런데 제가 알기로는 이게 SETH를 반증하는 건 아니죠?
SETH는 Strong Exponential Time Hypothesis(강한 지수 시간 가설)입니다.
https://en.wikipedia.org/w/index.php?title=Exponential_time_hypothesis&oldid=1378678795#Definition 을 보세요.
아니요, 반증하지 않습니다.
n의 1.9992제곱이면 실질적으로도 준이차라고 할 수 있나요? 엄밀히는 그렇죠. 그런데 이 결과에 실용적으로 쓸모가 있긴 한가요?