2026년 10월 26일, OpenAI가 공개 저장소에 67쪽 분량의 연구 논문을 올렸다. 표지에는 《The Exponential Time Hypothesis is False》(지수 시간 가설은 거짓이다)라는 간명한 제목이 적혀 있었다. 저자 이름에는 단 하나, “OpenAI”만 적혔다. 논문과 함께 린(Lean) 언어로 작성된 기계 검증 증명 코드 전체도 함께 공개되었다.
이론 컴퓨터 과학 분야에서 27년 동안 수백 편의 계산 복잡도 하한 연구를 떠받쳐온 핵심 가설이 결정론적 알고리즘 앞에서 무너졌다. 하지만 이번에 OpenAI는 자체적인 기술 승리를 일방적으로 선포하지 않았다. 연구소는 해당 가설을 처음 제안했던 석학들을 초빙하여 독립적인 전문가 검증망을 구성하도록 검증 권한을 넘겼다. 최첨단 이론 연구의 흐름 속에서, 인간은 다시금 ‘이해와 최종 판정’이라는 본질적인 역할로 돌아오고 있다.
결정론적 알고리즘으로 3-SAT 복잡도를 준지수 시간으로 단축
지수 시간 가설(ETH)은 1999년 러셀 임팔리아초(Russell Impagliazzo)와 라마모한 파투리(Ramamohan Paturi)가 처음 제안했다. 이 가설은 3-SAT 문제를 푸는 데 최악의 경우 $2^{\Omega(n)}$의 시간이 걸린다고 보았다. 지난 수십 년 동안 학계는 이 가설을 토대로 거대한 조건부 계산 복잡도 하한 체계를 구축해 왔다. 수많은 NP-완전 문제에 준지수 알고리즘이 존재하지 않는다는 판단 역시 이 가설의 방어선에 기대고 있었다.
OpenAI 논문의 핵심 정리인 정리 1.1(Theorem 1.1)은 이 판도를 뒤집었다. 임의의 고정된 $k \ge 2$에 대한 $k$-CNF 논리식에서 해의 개수를 정확히 세는 결정론적 알고리즘이 존재함을 증명한 것이다. 알고리즘 실행 시간은 $(n+m)^{O_k(1)} \cdot 2^{O_k(\sqrt{n \log \log n / \log n})}$으로 상한이 잡혔으며, 절 밀도가 $m \le Dn$을 만족하는 조건에서는 이 상한이 $2^{O_{k,D}(\sqrt{n/\log n})}$까지 줄어든다.
그림: OpenAI 단독 저자 표기와 요약문이 담긴 논문 첫 페이지. 준지수 시간 복잡도 상한을 제시하며 지수 시간 가설을 반박하고 있다. 출처: 깃허브(openai/math 저장소)
이 알고리즘이 달성한 시간 복잡도는 수학적 상한에서 엄격하게 $2^{o(n)}$을 나타내며, ETH가 상정했던 엄격한 지수 장벽을 정의상 허물었다. 결정론적 알고리즘은 충족 가능성 여부를 판별할 뿐만 아니라, 다항 공간 안에서 해의 개수까지 정확하게 계산해 낸다. 대수적 구조를 활용해 불리언 제약식을 해결함으로써 기존 조합 탐색이 안고 있던 오랜 시간 병목을 우회했다.
새 알고리즘의 기술적 뼈대는 정확한 계산, 희소 패리티 검사, 다항식 보간법의 결합이다. 핵심 설계 요소는 ‘공유 선형 스케치’와 저차 다항식 치환이다. 이러한 기술 경로는 수많은 이론적 파생 결과를 낳았다. Max-$k$-SAT 문제는 이제 준지수 시간 안에 $OPT(F) - \varepsilon m$ 오차 범위로 근사할 수 있게 되었다.
그래프 이론의 여러 난제에 걸려 있던 하한 가설들도 연쇄적으로 흔들리고 있다. 독립 집합 세기와 고정된 색상 수의 그래프 색칠 문제가 $2^{o(v)}$ 시간 안으로 들어왔고, 완벽 매칭 수 계산도 결정론적 조건에서 $2^{o(v+e)}$로 단축되었다. ETH에 기대어 유지되던 일련의 조건부 난이도 경계선이 한꺼번에 힘을 잃으면서, 학계는 미세 복잡도 이론의 실제 한계를 다시 측정해야 하는 상황을 맞았다.
이론적 경계 긋기: 새 알고리즘은 다항 시간 환산을 넘어서지 못한다
복잡도 가설이 흔들리면 개념적 혼선이 뒤따르기 쉽다. 논문이 공개되자마자 커뮤니티에서는 이번 알고리즘이 P=NP를 시사하는 것이 아니냐는 추측이 번졌다. 이는 준지수 시간 경계의 전이 특성에 대한 오해에서 비롯된 것이다. 쏟아지는 관심 속에서 저자들은 논문 2쪽에서 명확한 이론적 선을 그었다.
그림: 주 정리와 알고리즘 복잡도 상한을 제시한 논문 2쪽. 해당 준지수 한계가 다항 시간 환산을 통해 NP 전체로 확장되지 않음을 선제적으로 밝히고 있다. 출처: 깃허브(openai/math 저장소)
논문은 알고리즘이 얻은 $2^{o(n)}$ 시간 경계가 일반적인 다항 시간 환산을 거쳐 전이되지 않는다고 명시했다. 전체 NP 문제군으로 확장하려면 훨씬 더 엄격한 $2^{n^{o(1)}}$ 형태가 필요하다. 이번 연구 결과는 P 대 NP 문제와 직접적인 관련이 없으며, OpenAI 또한 논문에서 P=NP에 관한 어떠한 주장도 펴지 않았다.
연구진은 이번 논문을 ‘원시 연구 자료’(raw research data)로 규정했다. 린 저장소에 완전한 기계 검증 증명 스크립트가 담겨 있지만, 기호 시스템이 기계적으로 읽힌다고 해서 인간이 그 수학적 원리를 곧바로 납득할 수 있는 것은 아니다. 학계 공동체가 소화할 수 있는 직관적인 개념 모델로 바꾸어 내려면 동료 학자들의 해석 작업이 반드시 필요하다.
형식 검증 도구는 논리적 추론 단계에 논리 비약이 없음을 보장한다. 하지만 왜 특정 다항식 보간법 조합을 선택했는가에 대한 통찰까지 제공해 주지는 못한다. 기계 증명은 계산 추론의 논리적 결함을 걸러낼 수는 있지만, 알고리즘 이면에 담긴 깊은 통찰을 스스로 만들어내지는 못한다. 바로 이 지점에서 인간 수학자의 인지적 노동이 반드시 요구된다.
가설 제안자들을 불러 심사 주도권을 맡기다
일반적인 기업 제품 발표와 달리, OpenAI는 독자적인 성과 홍보 방식을 내려놓았다. 연구 결과를 발표함과 동시에 논문의 진위 검증을 총괄할 최고 권위의 외부 심사 위원 명단을 공개했다. 심사 핵심 위원으로는 러셀 임팔리아초, 라마모한 파투리, 라이언 윌리엄스(Ryan Williams)가 위촉되었다.
이 명단에는 뚜렷한 학술적 의도가 담겨 있다. 임팔리아초와 파투리는 1999년 프랜시스 제인(Francis Zane)과 함께 ETH 가설을 세운 장본인이다. 라이언 윌리엄스는 회로 복잡도 하한 기법을 바탕으로 강한 지수 시간 가설의 특수 형태를 깨뜨렸던 대표적 학자다. 가설을 세운 사람과 가설을 가장 깊이 파고든 석학에게 문지기 역할을 맡김으로써, 기업의 일방적 선언을 엄밀한 동료 평가로 대체했다.
전문가 위원회의 독립적인 활동을 보장하기 위해 OpenAI는 실질적인 재정 지원책도 마련했다. 사이먼스 재단(Simons Foundation)에 500만 달러 규모의 특별 기금을 전달했으며, 전체 이론 과학 협력 기금 규모는 약 1,500만 달러에 이른다. 이 기금은 학술 토론회를 조직하고 연구자들이 알고리즘의 모든 수학적 세부 사항을 꼼꼼히 점검할 수 있도록 지원하는 데 쓰인다.
이처럼 신중한 태도는 2주 전의 뼈아픈 경험에서 비롯되었다. 10월 6일, OpenAI는 사전 검증을 거치지 않은 인공지능 논문 722편을 한꺼번에 인터넷에 공개했다가 테렌스 타오(Terence Tao)를 비롯한 석학들의 거센 비판을 받았다. 신뢰도가 떨어지는 방대한 논문이 학술 생태계에 쏟아져 들어와 동료 평가 자원을 낭비시켰다는 지적이었다.
세 가지 성과로 시험하는 세 가지 검증 모델
10월 26일 발표에서 OpenAI는 세 분야에 걸친 이론적 돌파구를 함께 공개했다. 학문 분야마다 지식을 검증하는 특성이 다른 점을 감안하여 세 가지 서로 다른 발표 경로를 설계했다.
컴퓨터 과학 분야의 ETH 반박 논문에는 ‘외부 전문가 지도와 오픈소스 공개’를 결합한 검증 방식을 채택했다. 자연어로 쓰인 논문과 린 검증 코드를 동시에 공개하여 전 세계 연구자들의 즉각적인 검증을 유도했다.
조화해석학 분야의 국소 평활화 가설(Local Smoothing Conjecture) 증명은 수학계의 자율적인 검토에 맡겨졌다. 이 결과는 10월 18일에 도출되어 19일에 린 검증을 마쳤다. 크리스토퍼 소기(Christopher Sogge)가 1991년에 제안한 유클리드 파동 방정식 가설이 모든 차원에서 성립함을 증명한 논문으로, 오랫동안 학계를 괴롭혀온 카케야 가설과 스타인 제약 가설까지 아우른다.
그림: 같은 날 공개된 조화해석학 논문 첫 페이지. 유클리드 파동 방정식 국소 평활화 가설의 전 차원 증명을 담고 있다. 출처: 깃허브(openai/math 저장소)
조화해석학 연구는 별도 위원회 없이 수학계 전체의 자율 검토에 맡겼다. 반면 고에너지 물리학 연구에 대해서는 철저한 비공개 보안 원칙을 세웠다. 4차원 상호작용 양자장론의 존재성 증명—밀레니엄 문제인 양-밀스 이론 존재성 문제와 직결되는 주제—은 전적으로 독립된 외부 팀에 넘겨졌다.
물리학 심사단은 2004년 노벨 물리학상 수상자인 데이비드 그로스(David Gross)가 이끌며 마이클 더글러스(Michael Douglas), 아서 재피(Arthur Jaffe) 등이 참여한다. 연구 자료와 모델 세부 정보를 언제 외부에 공개할지는 이 외부 심사단이 전권을 쥐고 결정한다. 기업이 발표 시점 통제권을 내려놓고 학술 제도의 엄격한 절차에 복종한 셈이다.
이러한 세 갈래 검증 방식은 네 가지 원칙을 바탕으로 한다. 전체 과정의 투명성을 유지할 것, 기반 인공지능 모델에 학술 저자 자격을 요구하지 않을 것, 외부 학자들의 연구 노력을 온전히 인정할 것, 외부 위원회의 학술적 결론에 기업이 개입하지 않을 것이다. 학문 분야마다 요구되는 이해의 문턱에 맞춰 검증 구조를 설계한 것은, 기계가 만들어내는 첨단 지식을 다루는 새로운 거버넌스 실험이다.
인간의 역할: 증명 생성에서 이해와 판정으로
10월 16일 모델이 텍스트로 증명 초안을 작성하고 17일 린 기계 검증을 통과하기까지 걸린 시간은 단 이틀이었다. 인간 연구진이 30년 가까이 쌓아 올린 장벽을 인공지능 모델은 수십 시간 만에 넘어섰다. 이러한 폭발적인 생산 속도는 전통적인 학술 출판 주기를 완전히 뛰어넘었으며, 기존 동료 평가 시스템에 전례 없는 압박을 가하고 있다.
그러나 코드가 린 컴파일러를 통과했다는 사실은 기호 논리 체계 내부에서 모순이 없음을 뜻할 뿐이다. 그 자체가 알고리즘의 정수를 파악하려는 인간의 지적 장벽을 해소해 주지는 않는다. 학술 공동체는 알고리즘 이면에 놓인 기하학적 직관을 정리하고 새로운 개념 체계로 정리하기 위해 앞으로도 수개월을 쏟아야 한다. 기계가 빈틈없는 논리 증명을 세워줄 수는 있지만, 그 의미를 인간 대신 이해해 줄 수는 없다.
이 때문에 첨단 연구를 둘러싼 권력 관계의 위치 이동이 조용히 일어나고 있다. 기호 탐색과 논리 증명 작업을 알고리즘 도구가 떠맡으면서 과학 탐구의 핵심 병목 지점이 바뀌었다. 인간 연구자가 증명의 조각들을 하나하나 맞추는 데 모든 힘을 쏟을 필요는 사라졌다. 학술 공동체의 가장 핵심적인 임무는 직관적 추상화, 가치 판단, 그리고 최종 판정으로 옮겨가고 있다.
이 67쪽짜리 논문이 최종 검증을 통과하든 그렇지 못하든, 지식 생산의 오랜 질서는 이미 흔들리기 시작했다. 가설 창시자들을 평가 자리에 앉힌 OpenAI의 결정은 알고리즘의 성과만으로 진리를 독점할 수 없음을 보여준다. 복잡한 진리를 찾아가는 여정에서 기계가 증명의 종착점에 먼저 도착할 수는 있다. 하지만 그 발걸음이 참된 발견인지 결정하는 최종 판정권은 여전히 인간의 이해를 공유하는 공동체의 손에 쥐어져 있다.
참고 링크:
- OpenAI Research: 《The Exponential Time Hypothesis is False》 논문 및 Lean 형식 검증 코드 저장소
- OpenAI Research: 《Local smoothing for the Euclidean wave equation》 논문
- 사이먼스 재단(Simons Foundation): 이론 컴퓨터 과학 및 수학 프런티어 공동 연구 협력 발표
