무슨 일이 있었나
OpenAI가 학계 연구자들과 함께 수학, 컴퓨터과학, 물리학 분야의 새 연구 결과를 소개했는데요. 비슷한 시기에 OpenAI의 수학 저장소(openai/math)에 제목이 꽤 도발적인 프리프린트가 하나 올라왔어요. 제목이 「The Exponential Time Hypothesis Is False」, 그러니까 ‘지수 시간 가설은 거짓이다’예요. 논문 날짜가 2026년 10월 25일이라 정말 나온 지 얼마 안 됐고, 학계 검증은 이제 막 시작된 단계예요. 이 점은 먼저 짚고 갈게요.
알고리즘 수업에서 P와 NP는 들어봤어도 ETH는 처음 듣는 분이 많을 거예요. 그런데 이 가설은 지난 25년 동안 ‘이 문제는 이보다 빨리 풀 수 없다’는 수많은 증명이 깔고 있던 주춧돌 같은 존재거든요. 정말 무너진다면 이론 컴퓨터과학 교과서의 꽤 많은 페이지를 고쳐 써야 할 수도 있어요.
ETH가 뭐냐면
먼저 3-SAT부터 볼게요. 참이나 거짓 값을 갖는 변수가 n개 있고, ‘x1 또는 not x2 또는 x3’처럼 변수 세 개짜리 조건(절)이 여러 개 주어져요. 모든 조건을 한 번에 만족시키는 참/거짓 조합이 있는지 묻는 문제가 3-SAT이에요. 가장 단순한 방법은 2^n개 조합을 전부 넣어 보는 거죠. 변수가 100개면 2^100가지라서, 우주가 끝날 때까지 돌려도 다 못 봐요.
물론 연구자들은 이보다 훨씬 똑똑한 방법을 찾아왔어요. 1999년 쇠닝(Schöning)의 랜덤 워크 알고리즘이 약 1.334^n이었고, 이후 PPSZ 계열 알고리즘은 약 1.307^n까지 내려왔어요. 그런데 잘 보면 밑이 2에서 1.3 근처로 줄었을 뿐, 여전히 ‘어떤 상수의 n제곱’ 꼴이에요. 지수 시간이라는 틀 자체는 못 벗어난 거죠.
ETH는 이 벽이 진짜 벽이라고 보는 가정이에요. 임팔리아초(Impagliazzo)와 파투리(Paturi)가 2001년쯤 정식화했어요. 쉽게 말하면 ‘3-SAT은 어떻게 풀어도 c^n (c>1) 꼴의 시간이 든다’는 주장이에요. 반대로 지수가 n보다 느리게 자라는 시간, 수식으로 2^{o(n)}을 ‘준지수(subexponential) 시간’이라고 하는데요. ETH는 3-SAT을 준지수 시간에는 못 푼다는 뜻이에요. 이번 논문은 바로 그게 가능하다고 주장하는 거고요.
헷갈리기 쉬운 부분: P = NP라는 뜻은 아니에요
여기서 ‘그럼 P=NP인가?’ 하실 수 있는데, 아니에요. 2^{o(n)}에는 2^{n/log n}이나 2^{√n} 같은 시간도 들어가거든요. 이건 다항 시간보다는 여전히 훨씬 느려요. 비유하자면 서울에서 부산까지 걸어가야 하던 게 자전거로 갈 수 있게 된 거지, 순간이동이 된 건 아니에요. ETH가 틀렸다고 해도 P≠NP는 여전히 풀리지 않은 문제로 남아요.
그럼 뭐가 흔들릴까
ETH가 중요한 건 미세 복잡도(fine-grained complexity) 연구의 바탕이라서예요. ‘이 문제를 이보다 빨리 풀면 ETH가 깨진다’는 식으로, ETH를 전제로 증명된 하한(최소 이만큼은 걸린다는 증명) 결과가 정말 많거든요.
- k-Clique: 그래프에서 크기 k짜리 완전 부분그래프를 n^{o(k)} 시간에 찾을 수 없다는 결과
- 평면 그래프 문제들: 2^{o(√n)}보다 빨리 풀 수 없다는 결과
- 해밀턴 경로, 외판원 문제(TSP) 같은 고전 문제의 정밀한 하한들
반대로 암호가 당장 깨지는 건 아니에요. RSA나 격자 기반 암호는 ETH가 아니라 소인수분해, 격자 문제처럼 각자 다른 문제의 어려움에 기대고 있거든요. 그리고 암호 문제를 SAT으로 바꾸면 변수 수가 키 길이보다 훨씬 많아져요. 그래서 준지수 알고리즘이 있어도 실제 공격으로 바로 이어지진 않아요.
업계 맥락: 큰 주장일수록 검증이 먼저예요
복잡도 이론에서는 판을 뒤집겠다는 주장이 종종 나왔어요. 2010년 데올랄리카(Deolalikar)가 P≠NP를 증명했다는 원고를 냈을 때도, 전문가들이 몇 주 만에 구멍을 찾아냈죠. 그래서 지금 가장 정직한 태도는 ‘흥미롭지만 아직 검증 중’이에요. 앞으로 지켜볼 건 세 가지예요. 증명의 핵심 아이디어가 뭔지, Lean 같은 형식 검증 도구로 확인됐는지, 그리고 복잡도 이론 연구자들이 어떻게 반응하는지요.
이 논문이 OpenAI 저장소에 올라왔다는 점도 눈여겨볼 만해요. AI 연구소들이 올림피아드 문제 풀이를 넘어 아직 답이 없는 연구 문제에 도전하는 흐름이 뚜렷해지고 있거든요. 그럴수록 ‘누가 어떤 방식으로 검증했나’가 더 중요해져요.
한국 개발자에게 주는 시사점
내일 당장 실무 코드가 바뀌진 않아요. 그래도 알아두면 좋은 게 몇 가지 있어요.
첫째, 코딩 테스트에서 배운 ‘NP-hard 문제는 결국 완전 탐색’이라는 감각은 여전히 맞아요. 이론상 최악의 경우와 현실에서 들어오는 입력은 다르거든요. 실제로 Z3 같은 SAT/SMT 솔버는 이미 수백만 변수짜리 산업 문제도 잘 풀어요.
둘째, 스케줄링, 배치 최적화, 형식 검증처럼 SAT 솔버를 쓰는 분야에 있다면 새 알고리즘이 실제로 쓸 만한 속도까지 나오는지 지켜볼 만해요.
셋째, AI와 수학 연구가 어디까지 함께 왔는지 감을 잡기 좋은 사례예요.
마무리
한 줄 정리: 25년 동안 사실상 참으로 여겨진 ETH를 반박한다는 논문이 나왔어요. 사실로 확인되면 미세 복잡도 이론이 크게 재편되지만, P=NP나 암호 붕괴와는 다른 얘기예요.
여러분은 이 주장이 검증을 통과할 거라고 보세요, 아니면 어딘가 구멍이 있을 거라고 보세요? 그리고 AI가 참여한 증명이라면 어느 정도까지 검증해야 믿을 수 있을까요?
🔗 출처: Hacker News