지수 시간 가설(ETH)의 붕괴: AI가 재정의하는 계산 복잡도의 경계

계산 복잡도의 성역이 흔들리다

컴퓨터 과학의 오랜 난제 중 하나인 '지수 시간 가설(Exponential Time Hypothesis, 이하 ETH)'이 최근 인공지능 모델들에 의해 반박되었다는 소식은 학계에 큰 충격을 던졌습니다 [1]. ETH는 특정 논리 퍼즐의 변수가 늘어날수록 문제를 해결하는 데 필요한 시간이 지수적으로 증가한다는 가설로, 우리가 무엇을 '계산하기 어렵다'고 정의하는지 결정짓는 핵심 지표였습니다 [1]. 그러나 OpenAI와 Anthropic이 각각 발표한 새로운 알고리즘은 이 문제를 '지수 이하(sub-exponential)' 시간 내에 해결할 수 있음을 시사하며, 기존의 계산 복잡도 이론에 의문을 제기하고 있습니다 [1, 2].

AI의 '증명 덤프'와 학계의 대응

이번 발견은 단순한 기술적 진보를 넘어, 과학적 발견의 방법론적 갈등을 수면 위로 끌어올렸습니다. MIT의 라이언 윌리엄스(Ryan Williams) 교수는 과거 OpenAI의 무분별한 증명 공개 방식을 '수학자들에 대한 DDOS 공격'이라 비판한 바 있습니다 [1, 4]. 연구 결과가 검증 과정을 거치지 않은 채 쏟아져 나올 때, 학계가 이를 소화하고 검증할 물리적·시간적 여유가 부족하기 때문입니다 [4].

흥미로운 점은 OpenAI의 대응 방식이 변화하고 있다는 것입니다. 이번에는 수학, 컴퓨터 과학, 물리학 등 분야별로 연구 그룹을 구성하거나 GitHub에 코드를 공개하는 등 보다 체계적인 협업 모델을 모색하고 있습니다 [1]. Anthropic 역시 Lean 4를 활용한 형식적 검증(formal verification)을 통해 AI가 도출한 증명의 논리적 완결성을 보완하려는 시도를 보였습니다 [2]. 이는 AI가 단순히 답을 내놓는 도구를 넘어, 인간 학자들과 함께 검증 가능한 과학적 아티팩트를 생성하는 과정으로 진화하고 있음을 보여줍니다 [1, 2].

불확실성과 암호학적 함의

물론 이러한 결과가 즉각적으로 기존 암호 체계를 무너뜨리는 것은 아닙니다. 윌리엄스 교수는 OpenAI 측에 암호 시스템에 미칠 영향에 대해 질의했으며, 현재까지는 즉각적인 보안 위협이 발견되지 않았다는 답변을 확인했습니다 [1]. 하지만 ETH가 거짓으로 판명될 경우, 지난 수십 년간 이 가설을 토대로 작성된 수많은 논문과 암호학적 기반을 재검토해야 하는 상황에 직면하게 됩니다 [1].

또한, 이번 성과가 '최적의 알고리즘'인가에 대해서는 회의적인 시각도 존재합니다 [1]. AI가 제시한 알고리즘이 이론적으로는 ETH를 반박할지라도, 실제 계산 환경에서의 효율성이나 범용성에는 여전히 한계가 있을 수 있기 때문입니다 [1, 2]. 그럼에도 불구하고, AI가 인간이 수십 년간 맴돌던 난제에 새로운 접근 경로를 제시했다는 사실은 부정할 수 없습니다 [1].

과학적 탐구의 새로운 기준을 향하여

AI가 수학적 난제를 해결하는 속도가 빨라질수록, 인간 연구자들은 '무엇을 연구해야 하는가'라는 근본적인 질문에 직면하게 됩니다. AI가 이미 '낮게 매달린 과일(low-hanging fruit)'을 빠르게 수확해 버리는 상황에서, 학계는 더 높은 수준의 과학적 질문을 던지도록 강요받고 있습니다 [1]. 결국 이번 ETH 반박 사건은 AI가 과학적 발견의 주체가 될 수 있음을 증명함과 동시에, 인간과 AI가 지식의 경계를 확장하기 위해 어떻게 협력하고 검증해야 할지에 대한 새로운 숙제를 남겼습니다.

검증에 사용한 자료

[1] Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean? | TechCrunch — TechCrunch · 원문
[2] formal-math/eth at main · anthropics/formal-math — github.com · 공식·1차 자료
[3] levent (@__alpoge__) on X — x.com · 독립 참고 자료
[4] Ryan Williams @rrwilliams.bsky.social (@rrwilliams) on X — x.com · 독립 참고 자료

링크된 자료는 사실 확인에 사용했으며, 분석과 해석의 책임은 본 사이트에 있습니다.