AI, 27년 된 컴퓨터과학 가설 반증
원제: An AI Breakthrough Has Made Decades of Computer Science Research ‘Irrelevant’
왜 중요한가
AI가 수십 년간 쌓인 이론 컴퓨터과학의 핵심 전제를 뒤집으며, 알고리즘 설계와 복잡도 연구 전반의 재정립을 촉발하는 분기점이 됐다.
2026년 10월 28일, OpenAI와 Anthropic이 각각 '지수 시간 가설(ETH)'을 반증했다고 발표했다. ETH는 27년간 복잡도 이론과 알고리즘 설계 연구의 핵심 전제였으며, 두 기업은 자연어 및 기계 검증 형식(Lean)으로 GitHub에 증명을 공개했다. 수십 년치 이론 컴퓨터과학 연구가 근본부터 흔들리고 있다.
ETH는 특정 문제를 푸는 데 드는 계산량이 문제 크기에 따라 지수적으로 증가한다는 가설로, 1999년 제안된 이후 복잡도 이론과 알고리즘 연구의 근간으로 자리잡아 왔다. OpenAI와 Anthropic은 이번 주 각각 이 가설이 거짓임을 AI를 통해 증명했다고 밝혔다.
Linköping University의 Peter Jonsson 교수는 2주 후 이론 컴퓨터과학 분야 최고 권위 학회인 IEEE Foundations of Computer Science에 논문을 발표할 예정이었으나, ETH 반증으로 해당 연구의 상당 부분이 '사망했다'고 표현했다. UC Santa Barbara의 Daniel Lokshtanov 교수는 반증이 확인될 경우 자신의 논문 약 50편이 '무의미해지거나' 전면 재검토가 필요할 것이라고 밝혔다. 그는 이를 '분야 한복판에 떨어진 거대한 폭탄'이라 묘사했다.
OpenAI는 ETH를 최초 제안한 UC Santa Barbara 연구진과 MIT 학자들에게 증명 검증 작업을 조율해 달라고 요청했으며, Google Form을 통한 자원봉사자 모집과 관련 학술 컨퍼런스 개최 비용 지원을 약속했다. 두 기업이 공개한 증명은 자연어와 Lean 형식 모두로 GitHub에 게시됐지만, 연구자들은 아직 독립적인 검증을 완료하지 못한 상태다.
IT University of Copenhagen의 알고리즘 연구그룹장 Thore Husfeldt는 올해 대부분의 시간을 쏟은 연구가 이제 '무관해졌다'고 말하면서도, 이번 결과를 '한 세대에 한 번 나올 성과'라고 평가했다. 그는 '완전히 어두운 방을 더듬던 수학자들에게 분야 전체가 갑자기 환히 밝혀진 것과 같다'며, 연구자들이 이제 새로운 탐구 공간을 갖게 됐다고 강조했다.