분석

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를 만드는 회사이며 두 논문 중 하나를 냈다.

핵심 요약

보여준 것과 보여주지 못한 것

준지수 시간은 다항 시간이 아니므로 두 연구소 모두 결과가 P 대 NP를 해결하지 않는다고 말하고, OpenAI는 속도 향상이 NP 문제 전반으로 확장되지 않는다고 한다. Lean 검증은 형식 명제의 논리를 확인하지만 검토자들은 원자료 공개와 연구자 회의를 요청했고 OpenAI가 수락했다고 AI Weekly는 전한다. 보도된 날짜는 AI가 자연어 논증을 찾은 것이 10월 16일, 이튿날 형식화, 논문 공개는 10월 26일이다.

칩과 암호: 확실한 것

ETH는 최악의 경우에 관한 가설이어서 당장의 영향은 이론과 이에 기댄 하한에 미친다. 칩 검증 가속이나 암호 약화는 장기적 추측이다. BeInCrypto와 Let's Data Science는 현재의 암호와 산업용 솔버는 영향이 없다고 하고, AI Weekly는 한 언론 기사를 오해의 소지가 있다고 평한 컴퓨터 과학자의 말을 전한다. HackerNoon은 저자들이 지면상으로 타원곡선에도 방법을 적용했다고 하지만 검증된 것은 보지 못했다.

확립되지 않은 점

비교 표

비교 표
항목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를 만든다. 투자나 보안 자문이 아니다.

출처

이 기사에서 오류를 발견하셨나요? 제보하기 · 정정 정책

OrigoTech 로고

새로 나온 앱 iPhone·iPad

OrigoTech가 iPhone·iPad 앱으로 나왔습니다

기사를 네이티브로 읽을 수 있습니다. 안 읽은 기사의 ‘새 글’ 표시, 기기 내 검색, 이미 불러온 기사의 오프라인 읽기를 지원합니다. 무료, 계정 불필요, iOS 17 이상이며 기사 사이에 광고가 표시됩니다.

Rekha 아이콘: 한 번의 획으로 그린 집

같은 저자의 작품 자체 홍보

손가락으로 그리는 오일러 경로

OrigoTech 저자가 만든 iPhone 게임 Rekha: 같은 선을 두 번 지나지 않고 한 번의 획으로 모든 점을 잇는다. 모두 풀 수 있는 500개의 도형이 준비되어 있다.

OrigoTech 뉴스레터

AI 도구 소식을 출처와 함께 정리한 주간 다이제스트.

다음 읽을거리