분석
OpenAI와 Anthropic, AI가 지수 시간 가설을 반증했다고 주장…증명은 아직 인증되지 않았고 속도 향상은 천문학적으로 큰 입력에서만 나타나
OpenAI와 Anthropic은 AI가 지수 시간 가설을 반증했다고 주장했다. Impagliazzo는 충격이라 했지만 검토는 진행 중이고 이득은 거대한 입력에서만 나타난다.
1990년대에 지수 시간 가설(ETH)을 공동 제안한 Russell Impagliazzo는 AI가 만들어 낸 반증을 매우 충격적인 소식이라고 말했다고 AI Weekly가 11월 7일 언론 보도를 인용해 전했다. 다만 신중한 해석이 필요하다. 10월 26일 발표된 OpenAI와 Anthropic의 논문 두 편은 3-SAT를 더 빠르게 푸는 알고리즘을 주장하지만, 검토자들은 자신들의 참여가 인증이 아니라고 말하고, 결과는 P 대 NP를 해결하지 못하며, 속도 향상이 무차별 대입을 앞서는 것은 저장 가능한 규모를 훨씬 넘는 입력에서만이다. 공개: Anthropic은 이 사이트의 기사 작성을 돕는 Claude를 만드는 회사이며 두 논문 중 하나를 냈다.
핵심 요약
- 주장: OpenAI의 67쪽 논문과 Anthropic의 49쪽 논문은 3-SAT를 2^o(n) 시간에 푸는 알고리즘을 제시하며 ETH에 반한다고 한다. AI Weekly에 따르면 두 곳 모두 AI의 기여가 컸고 증명을 Lean으로 검증했다고 밝혔다.
- ETH의 내용: 3-SAT는 준지수 시간에 풀 수 없다는 가설. P와 NP가 다르다는 추측보다 강하며 많은 알고리즘이 거의 최적임을 보이는 데 쓰인다고 Wikipedia는 설명한다.
- 지금까지의 검증: Impagliazzo, Ryan Williams, Ramamohan Paturi로 이뤄진 그룹이 내용을 살폈다. 공동 성명은 참여를 인증으로 받아들이지 말라고 했고, Williams는 커뮤니티가 함께 연구해야 할 낯설어 보이는 부분이 두세 군데 있다고 말했다.
- 실용적 범위: 외부 추정으로 무차별 대입을 앞서는 분기점은 OpenAI의 한계식에서 약 10^2,389개 변수, Anthropic의 5절 경우에서 약 10^10,000개 변수다. 현재의 SAT 솔버와 암호는 영향받지 않는다.
보여준 것과 보여주지 못한 것
준지수 시간은 다항 시간이 아니므로 두 연구소 모두 결과가 P 대 NP를 해결하지 않는다고 말하고, OpenAI는 속도 향상이 NP 문제 전반으로 확장되지 않는다고 한다. Lean 검증은 형식 명제의 논리를 확인하지만 검토자들은 원자료 공개와 연구자 회의를 요청했고 OpenAI가 수락했다고 AI Weekly는 전한다. 보도된 날짜는 AI가 자연어 논증을 찾은 것이 10월 16일, 이튿날 형식화, 논문 공개는 10월 26일이다.
칩과 암호: 확실한 것
ETH는 최악의 경우에 관한 가설이어서 당장의 영향은 이론과 이에 기댄 하한에 미친다. 칩 검증 가속이나 암호 약화는 장기적 추측이다. BeInCrypto와 Let's Data Science는 현재의 암호와 산업용 솔버는 영향이 없다고 하고, AI Weekly는 한 언론 기사를 오해의 소지가 있다고 평한 컴퓨터 과학자의 말을 전한다. HackerNoon은 저자들이 지면상으로 타원곡선에도 방법을 적용했다고 하지만 검증된 것은 보지 못했다.
확립되지 않은 점
- 검토 그룹의 증명 인증: AI Weekly에 따르면 대기 중.
- 실제 SAT 사례에서 쓸 만한 속도 향상: 입증되지 않음. 기준점은 천문학적.
- 암호나 칩 설계 도구에 대한 실용적 공격: 확립되지 않음.
- 월스트리트저널과 뉴욕타임스의 칩·암호 관련 서술이 추측을 넘는지: 직접 읽지 못함.
비교 표
| 항목 | 2026년 11월 7일 기준 공표 내용 | 출처 |
|---|---|---|
| 발표 | 2026년 10월 26일 논문 두 편(OpenAI 67쪽, Anthropic 49쪽) | AI Weekly |
| 주장된 결과 | 3-SAT를 2^o(n) 시간에, Lean으로 검증 | AI Weekly |
| 분기점 규모 | 약 10^2,389개 변수(OpenAI), 10^10,000(Anthropic 5절 경우) | AI Weekly |
| 검토자 | Impagliazzo, Williams, Paturi. 공동 성명은 인증이 아니라고 함 | AI Weekly |
| P 대 NP | 두 연구소 모두 미해결이라고 함 | Let's Data Science |
자주 묻는 질문
AI가 P=NP를 증명했나
아니다. 주장된 알고리즘은 준지수 시간이지 다항 시간이 아니며 두 연구소 모두 P 대 NP는 미해결이라고 말한다.
암호가 약해졌나
실제로는 아니다. 확인한 매체들은 현재의 암호는 영향이 없다고 하며 이득은 터무니없이 큰 입력에서만 나타난다.
증명이 확인됐나
아직 인증되지 않았다. 증명은 Lean으로 검증됐지만 검토자들은 참여가 인증이 아니라고 하며 검토가 이어지고 있다.
방법과 한계
출처는 2026년 11월 8일에 확인했다. 두 논문, Lean 파일, 원본 신문 기사는 읽지 못했고 AI Weekly, Let's Data Science, HackerNoon, BeInCrypto, Wikipedia에 의존했다. 공개: Anthropic은 이 사이트의 기사 작성을 돕는 Claude를 만든다. 투자나 보안 자문이 아니다.
출처
- AI Weekly: OpenAI's AI Disproof of 1998 ETH Shocks Co-Author Impagliazzo (확인일: 2026-11-08)
- Let's Data Science: OpenAI and Anthropic Broke a 1999 Conjecture. Both Found It on October 16. (확인일: 2026-11-08)
- HackerNoon: OpenAI and Anthropic claim AI has disproved a 27-year-old computer science hypothesis (확인일: 2026-11-08)
- BeInCrypto: OpenAI Says Its AI Refuted the Exponential Time Hypothesis. Is Bitcoin Safe? (확인일: 2026-11-08)
- Wikipedia: Exponential time hypothesis (확인일: 2026-11-08)