OpenAI가 2026년 10월 26일 연구 블로그에 올린 글 하나가 이론 컴퓨터과학계를 흔들고 있습니다. AI 모델이 계산 복잡도 이론의 기둥으로 여겨지던 Exponential Time Hypothesis(ETH, 지수 시간 가설)를 반증했고, 그 증명이 Lean(컴퓨터가 증명의 논리를 한 단계씩 검사하는 정리 증명 보조 도구)으로 형식 검증까지 마쳤다는 내용입니다. 같은 글에는 양자장론과 조화해석학에서 얻은 결과도 함께 실렸습니다. 다만 ETH가 틀렸다는 것이 곧 P = NP를 뜻하지는 않습니다. OpenAI 사장 Greg Brockman은 발표 당일 X에 "P는 여전히 NP와 같지 않을 가능성이 높다"는 글을 올려 성급한 해석을 경계했습니다. 이 글은 ETH가 무엇이고, 이번 결과가 무엇을 바꾸며 무엇을 바꾸지 않는지, 암호 체계와 AI 자체에 어떤 질문을 던지는지 차분히 짚습니다.
ETH는 왜 30년 동안 벽이었나
ETH는 Boolean 충족 가능성 문제, 즉 SAT(여러 조건으로 묶인 논리식을 모두 참으로 만드는 변수 조합이 있는지 묻는 문제)에 관한 추측입니다. 변수가 n개인 SAT 문제를 풀려면 변수 수에 대해 엄격히 지수적으로 늘어나는 시간이 든다, 다시 말해 사실상 모든 조합을 다 시험해 보는 것 말고는 의미 있는 지름길이 없다는 주장입니다. 약 30년 전 Russell Impagliazzo, Ramamohan Paturi, Francis Zane이 제안했고, 이후 수백 편의 논문이 이 가설을 참으로 전제하고 쓰였습니다. 그래프 이론, 계산 생물학, 데이터베이스, 계산 기하학 등 여러 분야에서 "ETH가 참이라면 이 문제도 이만큼 어렵다"는 식의 조건부 난해성 결과가 쌓였습니다.
그래서 ETH는 빛의 속도처럼 넘을 수 없는 물리 법칙에 가깝게 취급되었습니다. 한 필지 위에 도시를 통째로 지었는데 땅 자체가 가정과 다르다는 사실이 드러난 셈입니다. ETH에 기대어 세운 수백 편의 하한 결과는 이제 전제부터 다시 들여다봐야 합니다.
이 가설이 P 대 NP 문제와 얽혀 있다는 점이 파장을 키웁니다. P 대 NP는 답을 빠르게 검증할 수 있는 문제를 빠르게 풀 수도 있는지 묻는 질문으로, Clay Mathematics Institute가 상금을 건 7개 밀레니엄 문제 가운데 하나입니다. 그 뿌리는 깊습니다. Scott Aaronson의 개관 논문 'P =? NP'는 1955년 John Nash가 NSA에 보낸 편지에서 암호를 깨려면 키 길이에 대해 지수적인 탐색이 필요하다고 짚은 대목, 그리고 1956년 Kurt Gödel이 John von Neumann에게 보낸 편지에서 같은 질문의 핵심을 독립적으로 정식화한 대목을 출발점으로 꼽습니다. 50년 넘게 최고의 두뇌들이 NP-완전 문제의 다항 시간 알고리즘을 찾거나 그런 알고리즘이 없음을 증명하려 했지만 어느 쪽도 성공하지 못했고, 그 사이 "P는 NP와 다를 것"이라는 합의가 굳어졌습니다.
자물쇠와 스도쿠로 보는 P, NP, 지수 시간
수학 없이도 핵심은 잡을 수 있습니다. 문제를 두 가지 질문으로 나눠 보면 됩니다. 처음부터 답을 찾는 데 얼마나 걸리는가, 그리고 누군가 내민 답이 맞는지 확인하는 데 얼마나 걸리는가입니다.
먼저 다이얼 자물쇠입니다. 다이얼 하나에 0부터 9까지 숫자가 있다면 모든 경우를 시험해도 10번이면 됩니다. 다이얼이 늘면 경우의 수는 이렇게 불어납니다.
| 다이얼 수 | 최대 시도 횟수 |
|---|---|
| 1개 | 10회 |
| 2개 | 100회 |
| 3개 | 1,000회 |
| 10개 | 100억 회 |
다이얼 하나가 늘 때마다 경우의 수가 10배씩 뛰는 것이 지수적 증가입니다. 반면 빨래 분류는 다릅니다. 한 바구니에 10분이 걸리면 다섯 바구니는 그에 비례해 늘어날 뿐 수십억 년이 걸리지는 않습니다. 이것이 P, 즉 다항 시간(입력이 커져도 걸리는 시간이 예측 가능한 범위에서 늘어나는 문제)입니다.
스도쿠는 NP의 성격을 보여 줍니다. 빈 9x9 판을 채우는 일은 오래 걸리지만, 다 채운 판이 맞는지는 행, 열, 3x3 칸에 1부터 9가 한 번씩 있는지만 보면 몇 초면 끝납니다. 답을 빠르게 검증할 수 있는 문제들의 집합이 NP(비결정적 다항 시간)입니다. 직원 근무표를 짜는 일도 마찬가지입니다. 서로 꺼리는 동료, 휴무 요청 같은 제약을 모두 만족하는 표를 처음부터 짜기는 어렵지만, 누군가 짜 온 표가 제약을 지켰는지는 금방 확인할 수 있습니다.
오늘날의 암호와 보안은 바로 이 틈을 의도적으로 이용합니다. 비밀번호와 암호 키는 추측하는 데 수천 년이 걸리지만 맞는지 확인하는 데는 수 밀리초면 됩니다. 만약 P = NP라면 답을 쉽게 검증할 수 있는 모든 문제에 똑같이 빠른 풀이 지름길이 있다는 뜻이 되고, 이 틈은 사라집니다.

▲ 풀기의 어려움과 검증의 쉬움
이번 결과가 바꾼 것과 바꾸지 않은 것
OpenAI가 공개한 논문 'The Exponential Time Hypothesis is False'의 핵심은 k-CNF 충족 가능성 문제를 준지수 시간, 정확히는 2^{o(n)} 시간에 푸는 결정적 알고리즘입니다. 모든 조합을 맹목적으로 시험하는 대신 탐색 공간을 효율적으로 누비는 알고리즘이 존재한다는 뜻입니다. 자물쇠에 비유하면, 다이얼을 하나씩 다 돌려 보는 대신 내부 장치의 소리를 듣고 제약을 추론해, 첫 다이얼이 9라는 사실만으로 뒤따르는 수백, 수천 가지 선택지를 한꺼번에 지워 버리는 방식에 가깝습니다. 논문에는 Lean으로 기계 검증한 형식 증명과 자연어 설명이 함께 실렸고, 문서에는 2026년 10월 17일 작성, 10월 25일 수정이라는 날짜가 적혀 있습니다. OpenAI에 따르면 AI 모델이 반증을 찾은 날은 10월 16일, Lean 형식화를 마친 날은 10월 17일입니다.
산을 넘는 비유가 이해를 돕습니다. A 지점에서 B 지점으로 가는 길에 에베레스트 같은 산이 놓여 있다고 해 보겠습니다. P가 NP와 다르다는 믿음은 정상까지 올라갔다 내려오는 최대의 수고를 반드시 치러야 한다는 뜻이고, P = NP는 산기슭을 평평하게 관통하는 터널이 있다는 뜻입니다. 수십 년간의 합의는 지면 높이의 터널은 없고 산을 통째로 넘어야 한다는 것이었습니다. ETH 반증이 보여 준 것은, 지면 터널의 존재는 여전히 확인되지 않았지만 산 중턱을 뚫고 지나가는 터널은 분명히 있다는 사실입니다. 사람 연구자들이 수십 년간 찾지 못한 지름길을 AI가 찾아냈다는 점이 이번 발표의 핵심입니다.
정리하면 이렇습니다.
- 바뀐 것: SAT 계열 문제에 지수 벽을 우회하는 알고리즘이 존재합니다. ETH를 전제로 한 조건부 난해성 결과는 더 이상 무조건 성립하지 않습니다.
- 바뀌지 않은 것: P 대 NP는 여전히 미해결입니다. 다항 시간 풀이가 있는지는 아직 모릅니다.
- 아직 모르는 것: 이론적 상한이 실제 소프트웨어의 속도 향상으로 이어지려면 상당한 후속 연구가 필요합니다. 이것이 실질적인 계산의 지름길인지, 이론의 경계를 조금 더 민 것인지도 검토 중입니다.
검증 방식과 발표 방식이 눈에 띄는 이유
이번 발표에서 눈여겨볼 대목은 결과 자체만큼이나 그것을 내놓은 방식입니다. OpenAI는 이 결과에 대해 공식 저자 명의를 갖지 않았습니다. 대신 분야의 대표 전문가들에게 검증과 안내를 맡겼습니다. ETH를 처음 제안한 UC San Diego의 Impagliazzo와 Paturi, 그리고 ETH의 강한 버전에 대한 반증과 알고리즘의 상한·하한을 밝혀 온 MIT의 Ryan Williams가 이 역할을 맡았습니다. 앞선 AI 발표들이 겪은 거센 반발을 피하려는 전략으로 보입니다. 한편 Anthropic도 거의 같은 시기에 매우 비슷한 결과에 도달한 것으로 보입니다.
수학계가 느끼는 불안도 감지됩니다. Aaronson은 수학자들이 "누가 우리 문제를 풀 수 있는지 정하는 심판이 아니다"라고 말하며, AI가 순수 수학에 들어오는 것을 막으려는 태도에 선을 그었습니다. 그는 OpenAI 발표 약 18시간 전 한 팟캐스트에서, 이론물리학자들이 전에는 AI가 자기 분야에 영향을 주지 않으리라 생각했지만 지금은 많은 이들이 AI의 놀라운 진전을 초조하게 지켜보고 있다고도 말했습니다.
암호 체계에 던지는 질문
Aaronson의 논문은 사실상 모든 현대 암호가 "복호화 키를 찾는 일은 다루기 힘든 NP 탐색 문제"라는 가정에 기대고 있다고 설명합니다. 인터넷으로 신용카드 번호를 안전하게 보내는 일도 결국 암호 문제를 거꾸로 푸는 것이 어렵다는 데 전적으로 의존합니다. 만약 P = NP가 증명되고 암호 탐색 문제가 다항 시간에 풀린다면 인터넷 보안, 전자 금융, 암호화폐가 심각하게 흔들리고 디지털 기반 전체를 다시 세워야 합니다.
하지만 지금 일어난 일은 그것이 아닙니다. ETH 반증은 P = NP의 증명이 아니며, 현대 암호가 이미 무너졌다고 결론 내리는 것은 성급합니다. 방어 관점에서 이번 논의가 다시 확인해 주는 교훈은 단순합니다. 비밀번호는 복잡한 문자보다 길이를 늘리는 것이 중요합니다. 글자 하나가 더해질 때마다 공격자가 뒤져야 할 탐색 공간이 지수적으로 커지기 때문입니다.
같은 동전의 반대 면도 있습니다. 어려운 조합 문제에 지름길이 있다면 물류 일정, 공급망 최적화, 반도체 칩 배치 같은 거대한 최적화 문제가 훨씬 쉬워지고, 단백질 구조 예측과 신약 설계 같은 생화학 공학도 전례 없이 빨라질 수 있습니다. OpenAI의 한 연구자는 물리학, 수학, 컴퓨터과학의 근본적 돌파구가 AI 발전 자체를 가속하는 순풍이 될 것이라고 말했습니다. 이번 결과가 AI 자체에 던지는 질문은 바로 이 지점입니다. AI가 찾은 이론이 AI를 더 빠르게 만드는 되먹임이 실제로 작동할지는 앞으로 지켜볼 일입니다.
상수의 문제와 시뮬레이션 사고실험
P 대 NP가 풀린다고 해서 곧바로 실용적이라는 보장은 없습니다. 알고리즘이 수학적으로는 다항 시간이면서도 상수 인자가 천문학적으로 커서 현실에서는 쓸 수 없을 수 있기 때문입니다. 자릿수가 많은 자물쇠를 예로 들면, 손으로 수천 년을 돌려야 하는 크기가 되어서야 비로소 효율이 나타나는 알고리즘은 실제로는 거의 쓸모가 없습니다.
여기서 흥미로운 사고실험이 나왔습니다. 한 사용자가 X에 올린 글은, P = NP가 참이지만 우리 세계의 거주자가 접근할 수 없을 만큼 거대한 상수가 붙어 있다면 가장 합리적인 결론은 우리가 설계된 시뮬레이션 속에 살고 있다는 것이라고 주장했습니다. 댓글에서는 게임 개발자가 속도 제한을 걸거나 빛의 속도에 상한을 두는 것에 빗댄 반응이 이어졌습니다. 과학적 결론이 아니라 재미있는 사고실험으로 받아들이는 것이 적절해 보입니다.
P = NP를 믿는 소수 의견
반대로 P = NP를 믿는다고 공개적으로 밝힌 학자도 있습니다. Northeastern University의 컴퓨터과학 교수 Emanuele Viola는 2018년 'I Believe P=NP'라는 글에서 계산의 역사를 근거로 들었습니다. 1950년대 Andrey Kolmogorov는 n비트 정수 곱셈에 제곱 시간이 필요하다고 추측했지만, 23세의 제자 Anatoly Karatsuba가 일주일 만에 더 빠른 알고리즘으로 이를 뒤집었습니다. 1968년에는 Volker Strassen이 행렬 곱셈에서 기존 방법이 최적이라는 가정을 깨고 더 빠른 알고리즘을 찾았습니다. 수학자들이 거듭 하한과 불가능을 선언했지만 새로운 알고리즘이 번번이 그 한계를 넘어섰고, 인류가 효율적 계산의 범위를 크게 과소평가해 왔다는 것이 그의 논지입니다. 이번 ETH 반증은 이 관점과 잘 맞아떨어지는 사례로 해석할 수 있습니다.

▲ 암호의 안전성과 최적화의 가능성
같은 발표에 실린 다른 결과들
OpenAI의 글에는 ETH 반증 외에 두 가지 결과가 더 있습니다. 하나는 양자색역학과 표준 모형의 완성에 관한 것으로, Tadeusz Bałaban의 구성적 양자장론 접근을 바탕으로 순수 Yang-Mills 이론의 존재를 수학적으로 엄밀하게 증명했다는 내용입니다. Lean 형식화는 2026년 10월 16일에 마쳤습니다. 이는 Clay Mathematics Institute의 밀레니엄 문제인 Yang-Mills 존재와 질량 간극 문제의 주요 부분을 다루지만, 공식 문제 전체의 해결은 아닙니다. 다른 하나는 조화해석학의 국소 평활화와 Kakeya 추측에 관한 결과로, 1991년 Christopher Sogge가 제기한 문제에서 비롯한 것입니다.
7개 밀레니엄 문제 가운데 이번 논의와 관련된 다섯 문제의 상태는 다음과 같습니다.
| 문제 | 상태 |
|---|---|
| Poincaré 추측 | 2002~2003년 Grigori Perelman이 해결, 그는 $100만 상금을 거절 |
| Navier-Stokes 존재와 매끄러움 | 약 30일 전 OpenAI가 해석적 증명과 Lean 형식화 발표, 학계 심사 진행 중 |
| P 대 NP | 미해결 |
| Riemann 가설 | 미해결 |
| Yang-Mills와 질량 간극 | 미해결, AI가 순수 Yang-Mills 존재 증명으로 일부 진전 |
최근 약 90일 사이에 AI 모델이 오랜 수학 문제 여러 개에 증명이나 반증을 내놓았다는 점은, 어떤 결론을 내리든 그 속도만큼은 사실로 받아들여야 할 대목입니다.
정리: 과장도 무시도 말아야 할 때
이번 발표를 한 문장으로 줄이면 "AI가 ETH를 반증했고, Lean으로 검증됐으며, P 대 NP는 그대로 미해결"입니다. 암호 체계가 당장 무너진 것은 아니지만, 30년간 수백 편의 논문이 딛고 선 전제가 틀렸다는 사실은 이론 컴퓨터과학에 작지 않은 재정비를 요구합니다. 독자 입장에서 할 일은 다음과 같습니다.
- 복잡도 관련 소식을 접할 때 ETH 반증과 P = NP 증명을 구분합니다. 전자는 준지수 알고리즘을 허용하지만 P와 NP를 하나로 합치지는 않습니다.
- AI가 만든 수학 결과를 평가할 때는 Lean 같은 정리 증명 보조 도구로 형식 검증을 거쳤는지 확인합니다. AI 모델이 자연어 증명과 Lean 코드를 함께 공개하는 경우가 늘고 있으니 관련 저장소의 움직임을 지켜볼 만합니다.
- 연구자라면 ETH에 직접 기대어 조건부 난해성을 주장한 결과를 다시 점검합니다. ETH 기반 환원은 더 이상 무조건 성립하지 않습니다.
- 이론적 알고리즘이 곧 배포 가능한 소프트웨어라고 가정하지 않습니다. 상수 인자와 지수가 현실적인지 따져 봐야 합니다.
- 보안 실무에서는 비밀번호와 키의 길이를 늘리는 원칙을 유지합니다. 지수적 탐색 공간은 여전히 방어의 근간입니다.
지름길이 진짜 열렸는지, 아니면 벽이 조금 뒤로 물러났을 뿐인지는 전문가들의 검토가 끝나야 알 수 있습니다. 분명한 것은 수십 년간 넘을 수 없다고 여겨진 벽에 AI가 구멍을 냈다는 사실이고, 그 구멍이 어디까지 이어지는지가 앞으로의 질문입니다.


