오픈AI·앤트로픽, 25년 된 지수시간가설 반증 주장

오픈AI(OpenAI)와 앤트로픽(Anthropic)은 10월 26일 인공지능(AI) 모델이 3-SAT를 지수 시간보다 빠르게 푸는 알고리즘을 찾아 지수시간가설을 반증했다고 각각 주장했다. 두 회사는 논문과 형식 증명을 공개했다.

발표 며칠 뒤 지수시간가설을 제안한 러셀 임팔리아초(Russell Impagliazzo)와 라마모한 파투리(Ramamohan Paturi), 이 가설을 의심해 온 라이언 윌리엄스(Ryan Williams) 매사추세츠공대 연구자가 AFP 인터뷰에 응했다. 세 사람은 연구의 의미와 독립 검토, 연구자에게 남을 역할을 두고 의견을 밝혔다.

지수시간가설은 특정 계산 문제의 입력 규모가 커질수록 문제를 푸는 데 필요한 시간이 지수적으로 늘어난다는 가설이다. 약 25년 전 제안됐으며 컴퓨터과학과 생물학 연구의 전제로 활용돼 왔다.

두 회사가 다룬 3-SAT는 여러 논리 조건을 모두 만족하는 답이 존재하는지 판정하는 문제다. 지수시간가설은 3-SAT를 최악의 경우 변수 수 n에 대해 2^{o(n)} 시간에 푸는 결정적 알고리즘이 없다는 가설이다.

오픈AI가 공개한 논문은 k-CNF 논리식의 해답 수를 정확히 세는 결정적 알고리즘을 제시했다. 논문 초고는 10월 17일 작성됐고, 수정본은 10월 25일 날짜로 공개됐다. 저자란에는 오픈AI만 기재됐다.

앤트로픽은 내부 연구용 클로드 모델이 3-SAT를 지수 시간보다 빠른 이론적 계산 범위에서 푸는 알고리즘을 찾았다고 밝혔다. 회사는 클로드가 작성한 논문과 Lean 4 형식 증명을 공개했다.

두 회사는 결과의 범위에도 선을 그었다. 앤트로픽은 자사 결과가 문제 규모가 매우 커질 때의 계산량을 다룬 점근적 성과이며, 실제 문제를 빠르게 푸는 성능을 뜻하지 않는다고 설명했다. 오픈AI도 이 결과가 모든 NP 문제에 지수 시간보다 빠른 알고리즘이 있다는 의미는 아니라고 논문에 적었다.

Lean은 형식화한 증명을 컴퓨터로 검사하는 도구다. 두 회사가 Lean 자료를 공개해 검사가 가능해졌다는 사실만으로 학계의 독립 평가가 끝난 것은 아니다.

이번 인터뷰에서는 같은 성과를 놓고 가설 제안자와 회의론자가 보인 반응이 드러났다.

임팔리아초는 “사고 과정을 설명할 수 있는 인간이 발견했으면 훨씬 좋았을 것”이라고 말했다. 그는 사람이 답에 이른 경로까지 설명할 수 있으며, 그 과정이 답만큼 중요할 때도 있다고 덧붙였다.

파투리는 첫 반응이 놀라움이었다고 말했다. 그는 이 가설을 바탕으로 한 지난 30년의 연구가 성과 발표로 사라지는 것은 아니라고 설명했다.

윌리엄스는 “나는 이 가설을 완전히 믿지 않았다”고 말했다. 그는 공개적으로 가설에 의문을 제기해 왔으며 이번 결과가 자신의 회의론을 뒷받침한다고 봤다.

세 연구자는 두 회사의 주장을 살필 독립 검토를 조직하는 데 참여하고 있다. 오픈AI도 임팔리아초와 파투리, 윌리엄스가 이끄는 외부 연구진이 증명을 검토할 예정이라고 밝혔다.

파투리는 연구의 경계를 넓히는 일과 그 방향을 정하고 발전시키는 일은 여전히 인간의 역할이라고 말했다. 그는 학생들에게 이런 도구를 익히면서 자신의 판단력도 기르라고 권했다. 윌리엄스는 이 분야가 큰 변화를 맞고 있지만 연구에 참여할 가치가 있다고 말했다.

임팔리아초는 지금은 연구에서 문제를 푸는 역할을 AI가 맡고, 사람은 검증과 설명을 담당하는 구도가 될 수 있다고 우려했다. 그는 AI가 더 발전하기 전까지 인간 연구자에게 그 역할이 남을 것이라는 취지로 말했다.

파투리는 강력한 연구 도구의 접근권이 기업에 집중되면 누가 연구에 참여하고 먼저 도구를 쓰며 연구 주제를 정하는지가 문제가 된다고 지적했다. 그는 “기업의 발표가 동료 평가를 대신할 수 없다”고 말했다. 지수시간가설의 약자와 이더리움(ETH)의 티커는 모두 ETH지만, 약자만 같을 뿐 이번 연구는 이더리움과 관련이 없다.

임팔리아초는 이번 결과 자체가 정보보안 위협은 아니라고 말했다. 향후 연구가 이어지면 더 강한 암호화가 필요해질 수 있다고 덧붙였지만, 현재 암호가 깨졌다는 뜻은 아니라고 선을 그었다.