OpenAI가 지수 시간 가설(Exponential Time Hypothesis)이 틀렸다고 제목에서 밝힌 수학 논문을 공개했습니다. 증명이 맞다면 현대 이론 컴퓨터과학의 작업 전제 하나가 무너집니다. 어떤 표준적인 유형의 가장 어려운 논리 퍼즐은 모든 경우를 시도하는 것보다 훨씬 빠르게 풀 수 없다는 전제입니다. 발표된 수많은 난이도 관련 결과가 이 가설에 기대고 있으므로, 반증이 확인되면 분야 전체가 다시 생각해야 합니다.
2026년 10월 17일 자로 작성되고 10월 25일에 수정된 이 논문은 GitHub에 있는 OpenAI의 공개 수학 저장소에 올라 있으며, 개인 저자 없이 OpenAI 이름으로만 되어 있습니다. 저장소 설명에 따르면 이곳의 원고들은 이름이 공개되지 않은 OpenAI 내부 모델이 만들었으며, 완성된 논문이 아니라 원자료 형태의 연구 데이터로 봐야 합니다. 60쪽이 넘는 이 논문의 주정리는 2 이상의 임의의 고정된 k에 대해, k-CNF 식(최대 k개 항으로 된 절들로 이루어진 논리식)을 만족하는 모든 할당을 세는 결정론적 알고리즘을 제시합니다. 실행 시간은 대략 2의 n/√(log n) 제곱으로 늘어나며(n은 변수 개수), 메모리 사용량은 다항식 수준에 머뭅니다. 이는 다항 시간보다는 느리지만 상수 곱하기 n을 지수로 하는 어떤 2의 거듭제곱보다도 빠르며, 바로 이 가설이 불가능하다고 본 속도입니다. 해를 세는 일은 해가 있는지 판정하는 일보다 어렵기 때문에, 이 결과는 가설의 계수 버전도 반증하며 논문 주장대로라면 더 강한 관련 가설들도 반증합니다.
방법은 대수적입니다. 저희가 서론을 읽은 바로는, 변수를 여러 그룹으로 나누고 식을 낮은 차수의 다항 방정식으로 바꾼 뒤 보간과 빠른 합산으로 공통 영점을 세는 방식이며, 기존의 split-and-list 기법과 포함-배제 기법을 바탕으로 합니다. 논문은 그래프 색칠, 독립 집합, 완전 매칭의 준지수 시간 정확 계수와 Max-k-SAT 근사 기법을 결과로 제시합니다. 다만 이런 형태의 시간 상한은 일반 적인 환원을 통해 옮겨지지 않으므로, 모든 NP 문제에 빠른 알고리즘이 생기는 것은 아니라고 신중하게 밝힙니다.
맥락을 보면 신중함이 필수입니다. 3-SAT에 대한 기존 최고의 정확 계수 알고리즘은 여전히 뚜렷한 지수 시간이 걸렸고, PPSZ 알고리즘과 그 개선을 포함한 수십 년의 연구도 지수의 밑을 아주 천천히 낮췄을 뿐입니다. 또한 논문의 따름정리 하나는 9월에 나온 다른 OpenAI 프리프린트인 The Unique Games Theorem에 기대고 있는데, 이 역시 검토를 거치지 않았습니다.
여기에 나온 어떤 것도 동료 검토를 거치지 않았고, OpenAI 자체 저장소도 Lean 형식 증명이 없는 결과에는 오류가 있을 수 있다고 경고하며, 계산 복잡도 이론 전문가들의 공개 반응도 저희는 아직 보지 못했습니다. 이 정도 규모의 결과는 전에도 발표되었다가 철회된 적이 있으며, 전문가들이 모든 보조정리를 검토한 뒤에야 빈틈이 드러나는 경우가 많았습니다. 지금 취할 태도는 믿지는 않되 관심을 두는 것입니다. 논문은 전문가들이 한 단계씩 검증할 수 있을 만큼 상세하며, 어떤 논평보다 그들의 판정이 먼저 이 문제를 결론지을 것입니다.