2026년 10월 26일, OpenAI는 내부 AI 모델이 이론 컴퓨터 과학의 기초적인 추측인 지수 시간 가설(Exponential Time Hypothesis, ETH)에 대한 반증 결과를 도출했다고 발표했습니다. 몇 시간 후, Anthropic은 자체 Claude 모델을 통해 동일한 결론에 도달했다는 논문을 게재하며 다른 방법을 사용했음을 밝혔습니다. 두 연구소 모두 시스템이 10월 16일에 핵심 결과를 발견했으며, Lean 형식화(formalization)를 공개했다고 전했습니다. 이 가설의 원래 제안자 중 두 명을 포함한 독립 전문가들이 해당 주장을 검토하고 있습니다.
지수 시간 가설이란 무엇인가
지수 시간 가설은 Russell Impagliazzo와 Ramamohan Paturi(Francis Zane와 함께)가 도입했으며, 3-SAT에 대한 준지수 시간 알고리즘이 존재하지 않는다고 주장합니다. 간단히 말해, 클래식 만족성 문제—클로즈 폭(width)이 3인 연결 정규형(conjunctive normal form)의 부울 공식이 만족 가능한지 여부를 결정하는 것—에 대해, 모든 올바른 알고리즘은 n개의 변수에 대해 최악의 경우 최소한 대략 $2^{\delta n}$ 시간($\delta > 0$인 상수)을 요구한다는 것입니다.
ETH는 그래프 알고리즘, 미세 복잡도(fine-grained complexity), 데이터베이스 등 여러 분야에 걸쳐 수백 개의 조건부 난이도 결과의 기반이 됩니다. 만약 ETH가 거짓이라면, 그 중 많은 조건부 하한 경계들이 붕괴되거나 다른 가정 위에서 재구축되어야 합니다. 이는 P ≠ NP보다 엄격하게 강하며, ETH를 반증하는 것이 P 대 NP 문제를 해결하지는 않지만, 광범위하게 사용되던 장벽을 제거합니다.
OpenAI의 주장된 결과
OpenAI는 “지수 시간 가설은 거짓이다(The Exponential Time Hypothesis is False)”라는 제목의 프리프린트를 공개했습니다. 회사에 따르면, 미공개 내부 모델이 10월 16일에 자연어 논증을 발견했고 다음 날 Lean으로 형식화되었습니다. 주장된 알고리즘은 결정론적이며 다항식 공간(polynomial space)을 사용하고, 임의의 고정 폭 k-CNF 공식의 만족하는 할당 개수를 대략 $(n + m)^{O(1)} \cdot 2^{n / (\log n)^{(1/2 + o(1))}}$ 시간 내에 계산합니다.
3-SAT은 특수한 경우이므로, 이는 ETH를 반증할 수 있습니다. Lean 개발 자료를 포함한 관련 자료들은 OpenAI의 공개 수학 저장소에 게시되었습니다. OpenAI는 Russell Impagliazzo, Ramamohan Paturi, 그리고 MIT의 Ryan Williams에게 이 주장에 대한 개방적인 검토를 조직하도록 요청했습니다. 해당 그룹은 자신들의 참여가 인증으로 해석되어서는 안 된다고 밝혔습니다.
Anthropic의 동시 주장
Anthropic은 Claude (Anthropic)이 저자로 기재된 “A $2^{o(n)}$ Time Algorithm for 3-SAT”라는 논문을 발표했습니다. 이 논문에 따르면, 내부 연구 모델이 10월 16일에 “인간의 개입 없이 14M 출력 토큰으로” 핵심 알고리즘을 발견했다고 합니다. Anthropic은 그 결과가 OpenAI의 주장과 독립적이며 동시에 발생한 것이며, Claude의 문헌 검색을 통해 ETH 또는 더 강력한 가설에만 의존하는 결과를 가진 800개 이상의 논문을 식별했음을 언급했습니다.
Anthropic의 접근 방식은 OpenAI와는 다르다고 설명됩니다. Anthropic 역시 OpenAI처럼 Lean 4 형식화(formalization)를 제공했습니다. 이 논문은 개선 사항이 점근적(asymptotic)이며 현실적인 공식 크기에 대한 실용적인 알고리즘을 도출하지 못한다고 강조합니다. 한 분석에 따르면, 새로운 방법론은 약 10백만 개 이상의 변수를 가진 입력에서만 완전 탐색(exhaustive search)보다 우수할 수 있다고 합니다.
검증 상태 및 전문가 반응
두 주장 모두 기계로 확인된 Lean 증명서가 첨부되어 있지만, Lean이 검증하는 것은 형식적 명제가 형식적 전제로부터 도출되는지 여부뿐입니다. 이는 해당 명제가 비형식적인 주장을 정확하게 포착했는지, 또는 근본적인 머신 모델과 복잡도 측정이 의도된 것인지를 자동으로 확인해주지는 않습니다. 2026년 10월 말 기준으로, 두 증명서 전체에 대한 독립적인 인간 검증은 발표되지 않았습니다.
임파글리아조(Impagliazzo)는 이 상황이 아직 100% 확실하지 않다고 설명했습니다. Williams와 다른 연구자들은 많은 ETH 기반 논문들이 즉시 무효화되지는 않지만, 연구자들이 더 약한 가정 하에서 어떤 결과가 살아남는지 재검토해야 할 것이라고 지적합니다. 초기 논평 중 일부는 Lean 경계(bounds)와 자연어 논문 사이의 가능한 격차를 강조했으며, 한 기술 노트에서는 구체적인 알고리즘이 천문학적으로 큰 입력에 대해서만 무차별 대입(brute force)보다 빨라진다고 주장했습니다.
OpenAI는 또한 같은 날 두 가지 추가 결과를 발표했는데, 하나는 Kakeya 문제와 관련된 조화 해석학(harmonic analysis) 분야의 것이고 다른 하나는 양-밀스 이론(Yang–Mills) 및 QCD 존재에 관한 물리학 분야의 것입니다. 이 결과들은 별도의 전문가 프로세스를 통해 처리되고 있습니다.
실질적 시사점 (Practical Implications)
이론 컴퓨터 과학자들에게 이 주장들이 사실로 입증된다면, 지난 20년 이상 해당 분야를 형성해 온 조건부 난이도 결과(conditional hardness results)에 대한 광범위한 재평가를 강요할 것입니다. 정확한 솔버(exact solvers)나 세밀한 알고리즘(fine-grained algorithms)을 개발하는 개발자 및 엔지니어들은 새로운 점근적 도구(asymptotic tools)를 얻게 되겠지만, 이 결과들이 현재 인스턴스 크기에 대한 SAT의 실질적인 난이도를 즉시 변화시키지는 않습니다.
더 넓은 관점에서 볼 때, 이 사건은 형식적 추론 작업(formal reasoning tasks)에서 최전선 모델(frontier models)의 가속화되는 능력을 보여주는 동시에, AI가 생성한 수학을 어떻게 발표하고 검토하며 출처를 표기해야 하는지에 대한 여전히 열려 있는 질문들을 보여줍니다. 두 경쟁 연구소(lab)가 같은 날 기계 검증된 형식화(machine-checked formalizations)를 갖춘 매우 유사한 결과를 발표했다는 사실은 독립적인 발견, 검증 파이프라인(verification pipelines), 그리고 "목자"(shepherds)로서 인간 전문가의 역할에 대한 논의를 심화시켰습니다.
이 점이 중요한 이유 (Why This Matters)
증명들이 궁극적으로 검토를 통과하는지 여부와 관계없이, 이 발표는 인공지능(AI)과 순수 이론 컴퓨터 과학의 교차점에서 주목할 만한 순간을 기록했다. 지난 27년간 연구를 조직해 온 하나의 추측(conjecture)이 이제 내부 AI 시스템의 작업으로 인해 활발한 전문가 검토를 받고 있다. 그 결과는 복잡도(complexity)의 수학적 기초와 AI가 지원한 과학적 결과를 출판하기 위한 진화하는 규범 모두에 영향을 미칠 것이다.
참고 자료 (Sources)