OpenAI·Anthropic 모델, 오랜 난제였던 Exponential Time Hypothesis 반증

OpenAI와 Anthropic이 모두 계산 복잡도 이론의 오랜 추측인 Exponential Time Hypothesis를 반증한다고 주장하는 AI 기반 결과를 발표했다.

10월 26일, OpenAI는 발표했다 자사 모델이 Exponential Time Hypothesis가 거짓이라는 증명을 만들어냈다고 밝혔다. 2000년대 초 제시된 이 가설은 3-SAT를 부분지수 시간에 풀 수 없다고 주장한다. 즉, 일부 일반적인 논리 퍼즐은 가능한 모든 답을 무차별 대입하는 것보다 훨씬 빠르게 풀 수 없다는 뜻이다.

이 가설은 널리 받아들여져 왔으며 매우 다양한 분야에서 조건부 계산 난이도 결과를 도출하기 위해 수백 편의 논문에서 활용돼 왔다. 따라서 이를 반증하면 해당 결과의 상당 부분이 무효화되고, 알고리즘·그래프 이론·계산 생물학 등을 포함한 여러 분야의 문제들이 지닌 계산 난이도를 연구자들이 재평가해야 한다.

이 AI 기업은 자사 모델이 10월 16일 자연어 형태의 반증을 생성했고, 다음 날 이를 Lean 수학 증명 보조기에서 형식화했다고 밝혔다. 두 결과 모두 공개 GitHub 저장소에서 확인할 수 있다.

OpenAI에 따르면 이 연구는 가설을 처음 제안한 연구자 중 두 명인 UC San Diego의 Russell Impagliazzo와 Ramamohan Paturi, 그리고 MIT의 Ryan Williams가 이끄는 외부 연구진의 검토를 받고 있다.

Williams는 X에서 밝혔다 연구자들이 이 발견이 실제로 어떤 의미를 갖는지 아직 파악하는 중이라고.

Williams는 "현재와 같은 진전 속도라면 앞으로 12개월 안에 실제 SAT 문제 해결에 관한 중요한 업데이트를 볼 가능성도 있다. 아니면 그런 일은 전혀 일어나지 않을 수도 있다. 정말 모르겠다"고 말했다.

한편 Anthropic은 공개했다 Exponential Time Hypothesis를 반증할 수 있는 방식으로 결정론적 알고리즘이 3-SAT를 해결한다는 내용을 담은 논문과 Lean 4 형식화를. 회사는 내부 Claude 연구 모델이 10월 16일 핵심 알고리즘을 발견했다고 밝혔다. 이날은 OpenAI 모델이 같은 발견을 내놓은 날이기도 하다. 이 과정에는 인간의 입력 없이 1,400만 개의 출력 토큰이 사용됐다.

Anthropic은 "이 결과는 순전히 점근적이며 실제로 수식을 해결하는 방법에 대해서는 아무것도 말해주지 않는다"고 지적했다.

한편 OpenAI는 AI가 생성한 다른 결과 두 가지도 공개했다. 하나는 조화 해석학에서 모든 차원에 대한 국소 평활화 추측의 증명이고, 다른 하나는 Quantum Chromodynamics와 순수 Yang-Mills 이론을 포함한 특정 양자장 이론이 존재한다는 수학적으로 엄밀한 증명이다.