OpenAI는 컴퓨터 분야에서 20여 년간 사용되어 온 중요한 이론인 '지수 시간 가설(ETH)'을 반증했다고 발표했다.

BlockBeats 소식에 따르면, 10월 27일 OpenAI는 자사의 AI 모델이 ETH를 "돌파"했다고 발표했으며, 이 소식은 기술계와 암호화폐 업계에서 빠르게 화제를 불러일으켰다. 하지만 특별히 설명해야 할 점은, 여기서의 ETH는 암호화폐 분야에서 널리 알려진 이더리움(Ethereum)이 아니라, 컴퓨터 과학에서 20여 년간 존재해 온 중요한 가설인 지수 시간 가설(Exponential Time Hypothesis, 약칭 ETH)이라는 것이다.

지수 시간 가설의 핵심 질문은 이것이다: "특별히 계산하기 어려운" 문제들은 대체 얼마나 어려운가?

일부 사람들이 들어본 "SAT 문제"(불리언 충족 가능성 문제)를 예로 들면, 이는 한 무더기의 논리 조건이 주어졌을 때 모든 조건이 동시에 성립하도록 하는 할당을 찾을 수 있는지를 묻는 것이다. 문제 규모가 커질수록 현재 알려진 최선의 방법은 기본적으로 가능한 답을 하나씩 시도하는 것뿐이며, 시간 비용은 규모에 따라 지수적으로 증가한다—흔히 말하는 "지수 시간"이다. ETH는 나아가 이러한 문제들은 본질적으로 크게 가속될 수 없으며, 진정한 의미의 "준지수 시간" 고효율 알고리즘은 존재하지 않는다고 단언한다.

이 가설은 1999년 제기된 이래로 이론 컴퓨터 과학의 중요한 초석으로 자리 잡아 왔다. 수백에서 수천 편의 논문이 이를 바탕으로 "어떤 문제는 어렵다", "어떤 알고리즘은 이미 최적에 가깝다"를 증명한다. 만약 ETH가 반박된다면, 우리가 "거의 더 빠르게 만들 수 없다"고 생각했던 많은 문제들에 이론적으로 더 나은 해법이 존재할 수 있음을 의미한다.

OpenAI는 이번에 자사 모델이 준지수 시간 내에 k-SAT 문제의 해의 개수를 정확히 계산할 수 있는 결정론적 알고리즘을 찾아냈으며, Lean으로 형식적 검증을 수행했다고 주장했다. 만약 이 결과가 최종적으로 전문가 검토를 견뎌낸다면, 지수 시간 가설을 직접적으로 흔들게 될 것이다.