Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?

🖼️ 인포그래픽

🖼️ 4컷 인포그래픽

💡 한 줄 요약

OpenAI와 Anthropic은 AI 모델이 지수시간 가설(ETH)을 반박하는 알고리즘을 찾았다고 주장했으며, 검증 결과에 따라 계산복잡도 연구의 전제와 기존 연구를 재검토해야 할 수 있다.

📌 핵심 요약

• 2026년 10월 27일 TechCrunch 보도에 따르면, OpenAI는 전날 오랫동안 연구자들을 괴롭힌 수학 문제 세 가지의 해법을 공개했으며 그중 하나가 지수시간 가설(ETH)의 반박이었다. Anthropic의 수학자 Levent Alpöge는 OpenAI가 기존 연구에 기반했다고 지적했고, Anthropic도 몇 시간 뒤 자체적인 ETH 반박을 공개했다.
• OpenAI는 분야별로 공개 방식을 달리했다. 수학 분야 결과는 GitHub에 공개했고, 컴퓨터과학계 작업반은 증명의 공개와 논의할 학술대회 지원을 요청했으며, 물리학계 작업반은 결과 공개 방식을 결정하기로 했다. MIT의 Ryan Williams는 ETH를 1999년 처음 발표한 Russell Impagliazzo, Ramamohan Paturi와 함께 해법 해석에 참여하고 있다.
• ETH는 특정 논리 문제에서 변수 수가 늘어날수록 가장 빠른 알고리즘도 지수적으로 증가하는 시간을 필요로 한다는 가설이다. OpenAI와 Anthropic은 이를 준지수 시간에 푸는 알고리즘을 제시했다고 주장한다. 사실이라면 ETH를 반박하지만, 빠르게 검증할 수 있는 모든 문제를 빠르게 풀 수 있다는 P = NP가 증명된 것은 아니다.
• Ryan Williams는 증명에 공동 검토가 필요한 낯선 부분이 두세 군데 있다고 설명했다. ETH 반박이 성립하면 지난 10여 년간 이를 전제로 삼은 많은 논문과 계산 난이도에 관한 직관을 재검토해야 하며, 그는 OpenAI의 알고리즘보다 더 나은 알고리즘이 나올 가능성도 있다고 봤다.
• Ryan Williams는 암호체계에 미칠 영향을 우선 확인했다. 그의 설명에 따르면 OpenAI는 검토 결과 이번 알고리즘이 암호체계의 붕괴를 뜻하지 않는다고 상당히 확신했지만, 개선된 알고리즘은 특정 키 길이에 의존하는 암호체계에 영향을 줄 수 있다. 그는 차세대 과학자 양성을 우려하면서도 AI가 연구자에게 더 야심 찬 질문을 요구한다는 점에는 낙관적이었다.

🧩 주요 포인트

1. 준지수 시간 알고리즘 주장 → ETH와 어려운 NP 문제에 대한 기존 직관을 흔들 수 있으나, P = NP의 성립 여부는 여전히 별도 문제다.
2. 증명 공개와 공동 검토 요구 → AI가 제시한 해법의 타당성 확인뿐 아니라 ETH에 의존한 연구와 AI의 과학 기여에 관한 규범을 함께 논의할 필요가 생겼다.
3. 암호체계 영향과 차세대 과학자 양성 → 현재 해법의 영향에 대한 평가와 함께, 알고리즘 개선 및 AI의 연구 능력 확대가 가져올 변화를 살펴야 한다.

🧠 상세 정리

1. ETH 반박 발표와 기존 연구 활용 논란

2026년 10월 27일 TechCrunch 기사에 따르면, OpenAI는 전날 오랫동안 연구자들을 괴롭힌 수학 문제 세 가지의 해법을 공개했다. 그중 예상 밖의 결과는 컴퓨터과학에서 무엇을 계산하기 어려운지 이해하는 데 큰 역할을 해온 지수시간 가설(ETH)의 반박 주장이었다. 과학계는 이전의 대규모 증명 공개 때처럼 흥분과 당혹감이 뒤섞인 반응을 보였다. Anthropic의 수학자 Levent Alpöge는 OpenAI의 해법이 기존 연구에 기반했다고 지적했으며, 몇 시간 뒤 Anthropic도 자체적인 ETH 반박을 공개했다. 기사는 두 연구소의 발표를 검증이 필요한 주장으로 다루며, ETH 반박이 확정됐다고 단정하지 않는다.

2. 분야별 공개 방식과 과학계의 공동 대응

OpenAI는 이번에 세 분야의 결과를 서로 다른 방식으로 공개하거나 공개를 준비했다. 수학 분야 결과는 GitHub에 올렸고, 컴퓨터과학계에서는 작업반이 구성돼 증명의 공개와 이를 논의할 학술대회에 대한 OpenAI의 지원을 요청했으며, 물리학계 작업반은 결과를 어떻게 공개할지 결정하기로 했다. 컴퓨터과학계의 대응을 이끄는 MIT 교수 Ryan Williams는 이달 초 OpenAI의 증명 일괄 공개를 수학자들에 대한 ‘DDOS 공격’이라고 비판한 인물이다. 그러나 그는 분야에 중요한 아이디어가 적절히 검토되도록 돕기 위해 협력하기로 했으며, 1999년 ETH를 처음 발표한 UC San Diego의 Russell Impagliazzo, Ramamohan Paturi도 해법 해석에 참여했다. 이들은 공개서한으로 연구자들의 의견과 AI의 과학 기여에 관한 규범 논의를 요청했고, Williams는 증명에서 낯설게 보이는 두세 부분 때문에 공동 검토가 필요하다고 설명했다.

3. P 대 NP와 ETH가 묻는 계산의 어려움

기사는 ETH를 이해하기 위해 먼저 P 대 NP라는 더 넓은 문제를 설명한다. 핵심 질문은 답이 맞는지 빠르게 검증할 수 있는 문제라면 그 답도 빠르게 찾을 수 있느냐는 것이다. 스도쿠는 완성된 답의 확인은 쉽지만 답을 찾는 데는 시간이 걸리는 사례로 제시되며, 암호 역시 열쇠가 있으면 내용을 확인할 수 있지만 암호를 깨는 데는 너무 오랜 시간이 걸린다는 설명이 이어진다. Williams는 P = NP가 빠르게 검증할 수 있는 모든 문제의 답을 빠르게 구할 수 있다는 주장이라며, 너무 좋은 이야기처럼 들리기 때문에 대부분의 과학자가 P ≠ NP를 가정한다고 말했다. ETH는 특정한 어려운 논리 문제에서 변수 수가 증가하면 가장 빠른 알고리즘에도 지수적으로 더 많은 시간이 필요하다는 가설로, 이러한 계산 난이도에 대한 관점을 뒷받침해 왔다.

4. 준지수 시간 알고리즘이 바꿀 수 있는 전망

OpenAI와 Anthropic의 주장은 해당 논리 문제들을 기존에 가능하다고 여겼던 속도보다 빠른 ‘준지수 시간’에 해결하는 알고리즘을 모델이 찾아냈다는 것이다. 주장이 맞는다면 ETH는 반박되지만, 그것만으로 빠르게 검증 가능한 모든 문제를 빠르게 풀 수 있다는 P = NP가 증명되는 것은 아니다. 기사는 이 결과가 더 일반적인 알고리즘으로 향하는 길을 열 가능성을 제시하면서도 결론을 확정하지 않는다. Williams는 컴퓨터과학자들이 P = NP의 개연성에 이전보다 조금 더 무게를 둘 필요가 있다고 보면서, 그 정도는 사람마다 다를 수 있다고 말했다. 그는 어려운 NP 문제의 해결 가능성에 관한 기존 직관이 흔들릴 수 있으며, OpenAI의 알고리즘이 최선일 수는 없다고 생각하기 때문에 이번 결과 역시 최종 답은 아닐 것이라고 덧붙였다.

5. 기존 논문의 재검토와 암호체계 영향

ETH는 오랫동안 유지된 가설이어서 지난 10여 년간 많은 과학 논문의 전제로 사용됐으며, 반박 주장이 성립하면 이 연구들을 다시 살펴야 한다고 Williams는 설명했다. 그가 OpenAI에 학술대회 지원을 요청한 이유도 알고리즘 자체의 이해를 넘어 여러 연구자의 작업과 분야의 기초가 어떻게 달라져야 하는지 함께 논의하기 위해서였다. 그는 학문적 영향에 앞서 사이버보안 문제를 확인했으며, OpenAI의 과학 책임자 Dan Roberts에게 현재 불안전해지는 암호체계가 있는지 물었다. Williams의 설명에 따르면 OpenAI는 이를 검토했고, 이번 결과가 암호체계의 붕괴를 뜻하지는 않는다고 상당히 확신했다. 다만 그는 개선된 알고리즘이 특정 키 길이에 의존하는 암호체계를 깨진 것으로 간주하게 만들 가능성은 있다고 말했다.

6. AI 시대의 연구 규범과 과학자 양성

기사는 AI가 과학적 발견을 주도하는 새로운 방식이 아직 정착 과정에 있다고 설명한다. Williams는 특히 차세대 과학자를 어떻게 길러낼지에 대한 실질적인 우려를 갖고 있지만, 전체적인 전망에는 낙관적이라고 말했다. 그는 고급 수학을 다루는 컴퓨터과학자라는 자신의 배경이 순수 수학자들보다 변화에 적응하는 데 도움이 됐을 수 있다고 봤다. 동시에 AI가 연구자들에게 기존보다 더 야심 찬 작업을 추구하도록 요구한다고 평가했다. 자신이 하던 연구가 AI에게 쉽게 해결되는 문제가 된다면 어떤 과학적 질문을 던져야 할지 기준을 높여야 한다는 것이 그의 설명이며, 이는 증명 검증과 공개 규범뿐 아니라 연구자의 역할과 교육에 관한 고민으로 이어진다.

🧾 핵심 주장 / 시사점

• ETH 반박의 타당성과 P = NP의 성립은 구분해서 이해해야 한다. 이번 주장은 계산 난이도에 관한 전망을 바꿀 수 있지만, 더 넓은 문제가 해결됐다는 결론까지 뒷받침하지는 않는다.
• ETH를 전제로 축적된 연구가 많다는 점에서, 검증의 영향은 새 알고리즘 하나의 평가를 넘어 기존 논문의 전제와 분야의 기초를 재검토하는 데까지 이어질 수 있다.
• Williams의 비판과 협력은 동시에 존재한다. 증명 공개 방식과 과학자 양성에 대한 우려를 유지하면서도, 공동 검토와 더 높은 수준의 연구 질문을 통해 AI의 기여를 수용하려는 태도다.

✅ 액션 아이템

• OpenAI와 Anthropic의 준지수 시간 알고리즘 및 ETH 반박 주장의 검증 결과 확인.
• ETH 반박이 성립할 경우 ETH를 전제로 한 기존 논문의 결론과 적용 범위 재검토.
• OpenAI의 현재 평가와 알고리즘 개선 가능성을 함께 고려해 암호체계 및 특정 키 길이에 대한 영향 검토.

❓ 열린 질문

• OpenAI와 Anthropic의 준지수 시간 알고리즘은 공동 검토를 거쳐 ETH를 반박하는 것으로 확인될까?
• ETH 반박이 성립하면 이를 전제로 한 기존 논문과 어려운 NP 문제에 대한 직관은 어떻게 달라질까?
• 개선된 알고리즘은 현재 OpenAI의 평가와 달리 특정 키 길이에 의존하는 암호체계에 영향을 줄 수 있을까?