OpenAI와 Anthropic이 각각 지수 시간 가설이 거짓임을 보이는 증명을 공개했습니다.
ETH는 이론 컴퓨터 과학에서 27년간 통용된 가정으로, 어떤 문제들은 힘으로 밀어붙이는(brute force) 방법보다 훨씬 빠르게는 결코 풀 수 없다고 말합니다. 이제 최상위 AI 연구소들이 그것이 사실이 아니라고 주장합니다.
증명이 검증을 견딘다면, 이는 현재까지 컴퓨터 과학에서 AI가 생성한 가장 중대한 결과가 됩니다. 또한 ETH를 사실로 전제한 수백 편의 연구 논문을 사실상 다시 생각하게 만듭니다.
이 글에서는 지수 시간 가설이 실제로 무엇을 의미하는지, 그리고 관련된 주제인 P 대 NP를 설명합니다. 아울러 두 연구소가 정확히 무엇을 주장하는지, 증명이 어떻게 확인되었는지, 암호학에 대해 무엇이 바뀌고 무엇은 바뀌지 않는지도 살펴봅니다.
쉬운 말로 보는 P 대 NP
P 대 NP는 답이 맞는지 검사하기 쉬운 모든 문제가 풀이도 쉬운지 묻습니다. 7대 밀레니엄 문제 중 하나이며, 이번 소식 이후에도 여전히 미해결입니다.
스도쿠가 고전적 비유입니다. 채워진 격자를 확인하는 데는 몇 초면 됩니다. 각 행, 열, 박스를 훑어 중복을 찾으면 되니까요. 반면 거의 빈 격자에서 해를 찾는 일은 훨씬 오래 걸릴 수 있으며, 격자가 커질수록 그 격차는 폭발적으로 커집니다.
- P는 컴퓨터가 다항식 시간에 풀 수 있는 문제들의 집합입니다. 입력 크기 n이 커질 때 작업량이 n2, n3처럼 증가하는 경우를 말합니다.
- NP는 제시된 해를 컴퓨터가 다항식 시간에 검증할 수 있는 문제들의 집합입니다.
P에 속하는 문제는 모두 NP에도 속합니다. 열린 질문은 그 역이 성립하느냐입니다. 다수의 컴퓨터 과학자는 P ≠ NP라고 믿습니다. 즉 어떤 문제들은 본질적으로 풀이가 검증보다 더 어렵다는 뜻입니다. 현대 암호학은 이 믿음에 기대고 있습니다. 암호화는 쉬워야 하지만, 키 없이 암호를 푸는 일은 어려워야 합니다.
지수 시간 가설이란?
ETH는 더 날카롭습니다. 한 가지 특정 NP 문제인 3-SAT는 알고리즘이 아무리 영리해도 지수 시간이 필요하다고 주장합니다. UC 샌디에이고의 Russell Impagliazzo와 Ramamohan Paturi가 1990년대 후반에 제안했으며, Francis Zane이 기초 작업에 기여했습니다.
3-SAT 문제
3-SAT에서는 n개의 참/거짓 변수와 절(clause) 목록으로 된 식을 받습니다. 각 절은 OR로 연결된 세 조건으로 이루어집니다. 예를 들어 "x₁은 참이거나 x₄는 거짓이거나 x₇은 참" 같은 식입니다. 목표는 모든 절을 동시에 만족시키는 변수 설정을 찾는 것입니다.
브루트 포스는 가능한 2ⁿ개의 설정을 모두 시도하므로, 변수가 하나 늘 때마다 작업량이 두 배가 됩니다. 대략 100개 변수쯤 되면 사실상 불가능해지는 이유입니다.
ETH가 말하는 것
ETH는 어떤 상수 c > 1이 존재하여, 어떤 알고리즘도 3-SAT를 cⁿ보다 빠르게 풀 수 없다고 말합니다. 영리한 알고리즘들이 밑(base)을 2보다 줄일 수는 있지만, 아예 준지수(subexponential)까지 낮추지는 못한다는 것입니다. 형식적으로는, δ > 0가 존재하여 3-SAT는 시간 O(2δn)에 풀 수 없다는 뜻입니다.
수십 년 동안의 진전은 이 그림과 일치했습니다. 연구자들은 밑을 계속 깎아내렸지만 1보다 훨씬 큰 상태였습니다. 3-SAT는 많은 다른 문제로 환원될 수 있기 때문에, ETH는 일꾼 가정으로 자리 잡았습니다. 연구자들은 이를 바탕으로 클리크(Clique), 정점 커버(Vertex Cover), 독립 집합(Independent Set) 등도 크게 더 빨리 풀 수 없다고 논증해 왔습니다.
새 결과의 비교
| 접근법 | 3-SAT 실행 시간 | 지수적으로 증가? |
|---|
| 브루트 포스 | 2ⁿ | 예 |
| 2026년 10월 이전 최선(결정적) | 약 1.328ⁿ | 예 |
| 2026년 10월 이전 최선(무작위화) | 약 1.308ⁿ | 예 |
| OpenAI와 Anthropic (2026년 10월) | 2^O(n log log n / √log n) | 아니오: 준지수 |
새 상한은 약기호로 2o(n)이라고 씁니다. 변수 하나가 늘 때 드는 비용의 밑이 n이 커질수록 1에 가까워지는데, 이는 ETH가 불가능하다고 말한 바로 그것입니다.
OpenAI와 Anthropic의 발표
두 연구소는 사실상 동일한 준지수 상한에 독립적으로 도달했고, 둘 다 Lean 증명 보조기를 사용해 기계로 확인한 증명을 논문에 첨부했습니다.
| | OpenAI | Anthropic |
|---|
| 논문 | "The Exponential Time Hypothesis Is False" (67쪽) | "A 2o(n) Time Algorithm for 3-SAT" (49쪽) |
| 모델 | 이름 미공개 내부 모델 | 내부 Claude 연구 모델, 저자로 표기 |
| 핵심 아이디어 발견 | 2026년 10월 16일 | 2026년 10월 16일 |
| 공개 시점 | 2026년 10월 26일 | 2026년 10월 26–27일 |
| 검증 | ETH를 여전히 반박하는 다소 약한 상한에 대한 Lean 증명 | Mathlib에 대한 Lean 4 증명, 두 번째 커널로 재검사 |
| 추가 주장 | 속도 향상이 NP 전체로 확장되지는 않음 | 강한 ETH(SETH)도 반박; 새로운 회로 하한 |
Anthropic은 Claude가 약 1,400만 토큰 분량의 출력을 생성한 뒤 인간의 개입 없이 핵심 알고리즘을 찾았다고 밝혔습니다. 그 방법은 텐서 네트워크와 랭크 논증을 사용합니다. 이후 연구자들이 최종 논문 작성에 도움을 주었습니다.
왜 두 연구소가 같은 날 찾았을까?
두 곳 모두 시기에 대해 설명하지 않았습니다. Anthropic의 논문은 두 결과가 독립적이면서 동시적이라고 밝히며, 두 글은 사실상 같은 상한에 도달하지만 수학을 전개하는 경로는 다릅니다.
맥락을 보면 겹침이 처음만큼 놀랍지는 않습니다. 두 연구소 모두 모델을 다수의 미해결 문제 목록에 적용하고 있었고, OpenAI만 해도 10월 초에 수백 편의 AI 생성 수학 원고를 공개했습니다. ETH는 이 분야에서 가장 잘 알려진 표적 중 하나이며, 두 모델은 동일한 공개 연구로부터 학습했습니다. 독립적이며 동시적인 발견은 과학에서 오래된 패턴이기도 합니다. 미적분의 뉴턴과 라이프니츠, 자연 선택의 다윈과 월리스처럼요.
증명의 견고함은?
Lean은 어떤 형식 명제가 공리로부터 논리적으로 따라옴을 확인합니다. 그 형식 명제가 논문과 동일한 내용을 말하는지는 확인하지 못합니다. Anthropic은 이 부합성을 기계가 확인하지 않는다고 명시했고, OpenAI는 자신의 Lean 파일이 헤드라인보다 다소 약한 상한을 증명한다고 말했습니다.
현재 ETH를 제안한 동일한 연구자들인 Impagliazzo와 Paturi, 그리고 MIT의 Ryan Williams가 형식 명제가 정말로 ETH를 포착하는지 평가하기 위한 워크숍을 조직하고 있습니다. 그들의 서한은 검토에 참여하는 것이 곧 지지를 의미하지는 않는다고 강조합니다. 이 글을 쓰는 시점까지는 공개적으로 오류가 발견되지는 않았습니다.
Williams는 OpenAI의 증명 중 일부는 통상적으로 보이지만, "두세 곳의 이질적으로 보이는 부분"은 여전히 면밀한 검토가 필요하다고 말했습니다. ETH의 공저자인 Impagliazzo는 이번 결과를 매우 놀랍다고 표현했습니다.
무엇이 바뀌고, 무엇은 바뀌지 않는가
실무적으로는 오늘 당장 거의 아무것도 바뀌지 않습니다(휴). 새 알고리즘들이 브루트 포스를 이기는 것은 컴퓨터가 담을 수 있는 것을 한참 넘어서는 엄청나게 큰 입력에서만 가능합니다.
더 빠른 SAT 솔버는 아님
Anthropic의 논문에 따르면 이 방법은 천문학적으로 큰 입력에서만 브루트 포스를 이깁니다. 변수 하나당 절이 다섯 개인 전형적인 식에서는 교차점이 자릿수가 약 1만 자리인 숫자입니다. 가장 일반적인 경우에는 자릿수가 대략 1억 자리인 숫자입니다.
저자들은 이 접근법이 대략 1천만 개 이하 변수에서는 도움이 될 가능성이 낮다고도 말합니다. 칩 검증, 스케줄링, 기획에 쓰이는 SAT 솔버가 이번 결과로 빨라지지는 않습니다.
암호는 깨지지 않았다
이 결과는 P 대 NP를 건드리지 않습니다. 아무도 그렇게 주장하지 않습니다. OpenAI는 이 알고리즘이 실제 암호시스템을 깨는지 확인했으며, 그렇지 않다고 꽤 확신한다고 밝혔습니다.
이론은 다시 쓰인다
더 큰 영향은 연구에 있습니다. ETH나 SETH 위에 세운 난이도 결과들은 이제 새로운 기반이 필요하며, 일부 연구자들은 자신의 수년간의 작업을 다시 들여다봐야 할 수 있다고 말합니다. 그렇다고 모든 것이 무너지지는 않습니다. Anthropic은 이번 결과가 많은 미세 복잡도 결과를 떠받치는 직교 벡터 문제를 반박하지는 않는다고 지적합니다.
AI에게 왜 중요한가
헤드라인의 핵심은 3-SAT 자체보다 누가 답을 찾았느냐입니다. 두 AI 시스템이 인간 전문가들이 한 세대 동안 신뢰해 온 추측을 독립적으로 뒤집었습니다.
연구 협력자로서의 AI
연구자들은 이제 일주일이나 이주 간격으로 새로운 AI 결과가 나와 진행 중인 프로젝트를 흔든다고 말합니다. Lean 같은 형식 도구가 중심이 되어가는데, 이는 사람이 기계가 쓴 긴 증명을 줄마다 다시 유도하지 않고도 신뢰할 수 있게 해주기 때문입니다.
숨은 지름길과 자기개선
ETH는 어떤 탐색 문제가 영리한 지름길이 없다는 믿음을 포착했습니다. 그 믿음이 틀렸다면, 겉보기에는 매우 어려운 다른 문제들에도 지름길이 숨어 있을 수 있습니다.
저는 재귀적 자기개선, 즉 더 나은 AI 설계를 돕는 AI 시스템이라는 아이디어에서 알고리즘 발견이 그런 지름길이 큰 의미를 가질 수 있는 영역이라고 봅니다. AI를 사용해 더 빠른 알고리즘을 찾는 일은 이를 향한 한 가지 구체적 경로이지만, 이번 결과가 당장 그것을 직접 이루는 것은 아닙니다.
데이터 실무자에게 의미하는 바
데이터로 만드는 사람들에게는 세 가지 교훈이 도드라집니다.
- 복잡도 이론은 학문에만 그치지 않습니다: 문제가 NP-난해함을 알면, 정확한 전수 탐색 대신 휴리스틱, 근사, 솔버를 고려해야 할 때를 구분할 수 있습니다.
- 검증은 역량입니다: AI가 더 많은 코드와 분석을 생성할수록, 그 출력을 (테스트, 증명, 재현 가능한 파이프라인으로) 확인하는 일은 생성만큼 중요해집니다.
- 점근적 분석은 오해를 부를 수 있습니다: 이론상 "더 빠른" 알고리즘이 실세계 규모에서는 무용지물일 수 있습니다.
결론
증명이 전문가 검토를 통과한다면, 지수 시간 가설은 거짓으로 드러난 널리 믿어진 추측(예: 오일러 거듭제곱 합 추측)의 짧은 목록에 합류합니다. 하지만 P 대 NP는 여전히 미해결이며, 암호는 당분간 안전합니다.
앞으로 주목할 이정표는 ETH 제안자들이 주도하는 검토 워크숍, 알고리즘의 독립적 재구현, 그리고 누군가 상한을 더 조이는지 여부입니다.
이러한 이야기의 토대를 쌓고 싶다면, 자료구조와 알고리즘, Python 프로그래밍, 기계 학습 과정을 살펴보세요. 이런 결과를 읽을 수 있게 해주는 빅오 표기 관점을 다룹니다.
OpenAI와 Anthropic이 각각 지수 시간 가설이 거짓임을 보이는 증명을 공개했습니다.
ETH는 이론 컴퓨터 과학에서 27년간 통용된 가정으로, 어떤 문제들은 힘으로 밀어붙이는(brute force) 방법보다 훨씬 빠르게는 결코 풀 수 없다고 말합니다. 이제 최상위 AI 연구소들이 그것이 사실이 아니라고 주장합니다.
증명이 검증을 견딘다면, 이는 현재까지 컴퓨터 과학에서 AI가 생성한 가장 중대한 결과가 됩니다. 또한 ETH를 사실로 전제한 수백 편의 연구 논문을 사실상 다시 생각하게 만듭니다.
이 글에서는 지수 시간 가설이 실제로 무엇을 의미하는지, 그리고 관련된 주제인 P 대 NP를 설명합니다. 아울러 두 연구소가 정확히 무엇을 주장하는지, 증명이 어떻게 확인되었는지, 암호학에 대해 무엇이 바뀌고 무엇은 바뀌지 않는지도 살펴봅니다.
쉬운 말로 보는 P 대 NP
P 대 NP는 답이 맞는지 검사하기 쉬운 모든 문제가 풀이도 쉬운지 묻습니다. 7대 밀레니엄 문제 중 하나이며, 이번 소식 이후에도 여전히 미해결입니다.
스도쿠가 고전적 비유입니다. 채워진 격자를 확인하는 데는 몇 초면 됩니다. 각 행, 열, 박스를 훑어 중복을 찾으면 되니까요. 반면 거의 빈 격자에서 해를 찾는 일은 훨씬 오래 걸릴 수 있으며, 격자가 커질수록 그 격차는 폭발적으로 커집니다.
P에 속하는 문제는 모두 NP에도 속합니다. 열린 질문은 그 역이 성립하느냐입니다. 다수의 컴퓨터 과학자는 P ≠ NP라고 믿습니다. 즉 어떤 문제들은 본질적으로 풀이가 검증보다 더 어렵다는 뜻입니다. 현대 암호학은 이 믿음에 기대고 있습니다. 암호화는 쉬워야 하지만, 키 없이 암호를 푸는 일은 어려워야 합니다.
지수 시간 가설이란?
ETH는 더 날카롭습니다. 한 가지 특정 NP 문제인 3-SAT는 알고리즘이 아무리 영리해도 지수 시간이 필요하다고 주장합니다. UC 샌디에이고의 Russell Impagliazzo와 Ramamohan Paturi가 1990년대 후반에 제안했으며, Francis Zane이 기초 작업에 기여했습니다.
3-SAT 문제
3-SAT에서는 n개의 참/거짓 변수와 절(clause) 목록으로 된 식을 받습니다. 각 절은 OR로 연결된 세 조건으로 이루어집니다. 예를 들어 "x₁은 참이거나 x₄는 거짓이거나 x₇은 참" 같은 식입니다. 목표는 모든 절을 동시에 만족시키는 변수 설정을 찾는 것입니다.
브루트 포스는 가능한 2ⁿ개의 설정을 모두 시도하므로, 변수가 하나 늘 때마다 작업량이 두 배가 됩니다. 대략 100개 변수쯤 되면 사실상 불가능해지는 이유입니다.
ETH가 말하는 것
ETH는 어떤 상수 c > 1이 존재하여, 어떤 알고리즘도 3-SAT를 cⁿ보다 빠르게 풀 수 없다고 말합니다. 영리한 알고리즘들이 밑(base)을 2보다 줄일 수는 있지만, 아예 준지수(subexponential)까지 낮추지는 못한다는 것입니다. 형식적으로는, δ > 0가 존재하여 3-SAT는 시간 O(2δn)에 풀 수 없다는 뜻입니다.
수십 년 동안의 진전은 이 그림과 일치했습니다. 연구자들은 밑을 계속 깎아내렸지만 1보다 훨씬 큰 상태였습니다. 3-SAT는 많은 다른 문제로 환원될 수 있기 때문에, ETH는 일꾼 가정으로 자리 잡았습니다. 연구자들은 이를 바탕으로 클리크(Clique), 정점 커버(Vertex Cover), 독립 집합(Independent Set) 등도 크게 더 빨리 풀 수 없다고 논증해 왔습니다.
새 결과의 비교
새 상한은 약기호로 2o(n)이라고 씁니다. 변수 하나가 늘 때 드는 비용의 밑이 n이 커질수록 1에 가까워지는데, 이는 ETH가 불가능하다고 말한 바로 그것입니다.
OpenAI와 Anthropic의 발표
두 연구소는 사실상 동일한 준지수 상한에 독립적으로 도달했고, 둘 다 Lean 증명 보조기를 사용해 기계로 확인한 증명을 논문에 첨부했습니다.
Anthropic은 Claude가 약 1,400만 토큰 분량의 출력을 생성한 뒤 인간의 개입 없이 핵심 알고리즘을 찾았다고 밝혔습니다. 그 방법은 텐서 네트워크와 랭크 논증을 사용합니다. 이후 연구자들이 최종 논문 작성에 도움을 주었습니다.
왜 두 연구소가 같은 날 찾았을까?
두 곳 모두 시기에 대해 설명하지 않았습니다. Anthropic의 논문은 두 결과가 독립적이면서 동시적이라고 밝히며, 두 글은 사실상 같은 상한에 도달하지만 수학을 전개하는 경로는 다릅니다.
맥락을 보면 겹침이 처음만큼 놀랍지는 않습니다. 두 연구소 모두 모델을 다수의 미해결 문제 목록에 적용하고 있었고, OpenAI만 해도 10월 초에 수백 편의 AI 생성 수학 원고를 공개했습니다. ETH는 이 분야에서 가장 잘 알려진 표적 중 하나이며, 두 모델은 동일한 공개 연구로부터 학습했습니다. 독립적이며 동시적인 발견은 과학에서 오래된 패턴이기도 합니다. 미적분의 뉴턴과 라이프니츠, 자연 선택의 다윈과 월리스처럼요.
증명의 견고함은?
Lean은 어떤 형식 명제가 공리로부터 논리적으로 따라옴을 확인합니다. 그 형식 명제가 논문과 동일한 내용을 말하는지는 확인하지 못합니다. Anthropic은 이 부합성을 기계가 확인하지 않는다고 명시했고, OpenAI는 자신의 Lean 파일이 헤드라인보다 다소 약한 상한을 증명한다고 말했습니다.
현재 ETH를 제안한 동일한 연구자들인 Impagliazzo와 Paturi, 그리고 MIT의 Ryan Williams가 형식 명제가 정말로 ETH를 포착하는지 평가하기 위한 워크숍을 조직하고 있습니다. 그들의 서한은 검토에 참여하는 것이 곧 지지를 의미하지는 않는다고 강조합니다. 이 글을 쓰는 시점까지는 공개적으로 오류가 발견되지는 않았습니다.
Williams는 OpenAI의 증명 중 일부는 통상적으로 보이지만, "두세 곳의 이질적으로 보이는 부분"은 여전히 면밀한 검토가 필요하다고 말했습니다. ETH의 공저자인 Impagliazzo는 이번 결과를 매우 놀랍다고 표현했습니다.
무엇이 바뀌고, 무엇은 바뀌지 않는가
실무적으로는 오늘 당장 거의 아무것도 바뀌지 않습니다(휴). 새 알고리즘들이 브루트 포스를 이기는 것은 컴퓨터가 담을 수 있는 것을 한참 넘어서는 엄청나게 큰 입력에서만 가능합니다.
더 빠른 SAT 솔버는 아님
Anthropic의 논문에 따르면 이 방법은 천문학적으로 큰 입력에서만 브루트 포스를 이깁니다. 변수 하나당 절이 다섯 개인 전형적인 식에서는 교차점이 자릿수가 약 1만 자리인 숫자입니다. 가장 일반적인 경우에는 자릿수가 대략 1억 자리인 숫자입니다.
저자들은 이 접근법이 대략 1천만 개 이하 변수에서는 도움이 될 가능성이 낮다고도 말합니다. 칩 검증, 스케줄링, 기획에 쓰이는 SAT 솔버가 이번 결과로 빨라지지는 않습니다.
암호는 깨지지 않았다
이 결과는 P 대 NP를 건드리지 않습니다. 아무도 그렇게 주장하지 않습니다. OpenAI는 이 알고리즘이 실제 암호시스템을 깨는지 확인했으며, 그렇지 않다고 꽤 확신한다고 밝혔습니다.
이론은 다시 쓰인다
더 큰 영향은 연구에 있습니다. ETH나 SETH 위에 세운 난이도 결과들은 이제 새로운 기반이 필요하며, 일부 연구자들은 자신의 수년간의 작업을 다시 들여다봐야 할 수 있다고 말합니다. 그렇다고 모든 것이 무너지지는 않습니다. Anthropic은 이번 결과가 많은 미세 복잡도 결과를 떠받치는 직교 벡터 문제를 반박하지는 않는다고 지적합니다.
AI에게 왜 중요한가
헤드라인의 핵심은 3-SAT 자체보다 누가 답을 찾았느냐입니다. 두 AI 시스템이 인간 전문가들이 한 세대 동안 신뢰해 온 추측을 독립적으로 뒤집었습니다.
연구 협력자로서의 AI
연구자들은 이제 일주일이나 이주 간격으로 새로운 AI 결과가 나와 진행 중인 프로젝트를 흔든다고 말합니다. Lean 같은 형식 도구가 중심이 되어가는데, 이는 사람이 기계가 쓴 긴 증명을 줄마다 다시 유도하지 않고도 신뢰할 수 있게 해주기 때문입니다.
숨은 지름길과 자기개선
ETH는 어떤 탐색 문제가 영리한 지름길이 없다는 믿음을 포착했습니다. 그 믿음이 틀렸다면, 겉보기에는 매우 어려운 다른 문제들에도 지름길이 숨어 있을 수 있습니다.
저는 재귀적 자기개선, 즉 더 나은 AI 설계를 돕는 AI 시스템이라는 아이디어에서 알고리즘 발견이 그런 지름길이 큰 의미를 가질 수 있는 영역이라고 봅니다. AI를 사용해 더 빠른 알고리즘을 찾는 일은 이를 향한 한 가지 구체적 경로이지만, 이번 결과가 당장 그것을 직접 이루는 것은 아닙니다.
데이터 실무자에게 의미하는 바
데이터로 만드는 사람들에게는 세 가지 교훈이 도드라집니다.
결론
증명이 전문가 검토를 통과한다면, 지수 시간 가설은 거짓으로 드러난 널리 믿어진 추측(예: 오일러 거듭제곱 합 추측)의 짧은 목록에 합류합니다. 하지만 P 대 NP는 여전히 미해결이며, 암호는 당분간 안전합니다.
앞으로 주목할 이정표는 ETH 제안자들이 주도하는 검토 워크숍, 알고리즘의 독립적 재구현, 그리고 누군가 상한을 더 조이는지 여부입니다.
이러한 이야기의 토대를 쌓고 싶다면, 자료구조와 알고리즘, Python 프로그래밍, 기계 학습 과정을 살펴보세요. 이런 결과를 읽을 수 있게 해주는 빅오 표기 관점을 다룹니다.