Anthropic, Claude로 ETH 반박 알고리즘 발견 발표

Anthropic이 내부 연구용 Claude 모델로 지수 시간 가설(ETH)에 반하는 알고리즘을 찾았다고 10월 27일(현지시간) 공개했다. OpenAI의 발표 직후였고, 두 회사의 공개는 약 6시간 간격이다.

공개물은 논문과 증명 검증 도구 린(Lean)용 코드이며 깃허브에 게시됐다. 논문 제목은 「3-SAT를 위한 준지수 시간 알고리즘」이고 저자란에는 사람 대신 '클로드(Anthropic)'만 적혔다. Anthropic의 레벤트 알푀게 연구원은 X에 글을 올려, 10월 16일 사람이 관여하지 않은 상태에서 모델이 해법을 찾았다고 주장했다. 발견 과정에서 AI가 만든 출력은 총 1400만 토큰이라고 알푀게 연구원은 설명했다. 발견 후 연구진이 Claude와 함께 내용을 논문으로 다듬었다.

결과의 내용과 파장

두 회사가 낸 결과는 논리식 만족성 문제의 대표격인 3-SAT를 준지수 시간(subexponential time)에 푸는 알고리즘이다. ETH는 이런 풀이가 불가능하다고 전제해 왔으므로, 결과가 맞다면 가설의 출발점이 흔들린다. 양측이 밝힌 발견일은 모두 10월 16일로 같고, 세부 방식은 서로 다르다.

OpenAI 모델은 10월 16일 증명을 찾았고 이튿날 린으로 검증했다. 라이언 윌리엄스 MIT 교수는 10월 26일 X에 OpenAI의 PDF 링크를 공유했다. 거기 담긴 OpenAI의 주장은 n개 변수의 3SAT를 약 exp(n/(log n)^{1/2+o(1)}) 시간에 풀 수 있다는 것이다. 윌리엄스 교수는 ETH 검증에 참여하는 중이다.

ETH에 의존한 연구가 수백 편이라고 OpenAI는 밝혔다. 결과가 검증되면 이 연구들을 다시 점검해야 할 수 있으며, 윌리엄스 교수도 비슷한 취지로 말했다. 윌리엄스 교수는 테크크런치 인터뷰에서 AI가 자신이 다루던 문제를 쉽게 풀게 된다면 어떤 질문을 던질지 기준을 얼마나 높일 수 있을지 자문했다.

배경과 한계

ETH는 1999년에 나온 가설로, 복잡한 논리 문제의 풀이 시간이 변수가 늘수록 기하급수로 불어난다고 본다. 알고리즘이 어디까지 빨라질 수 있는지 따질 때 근거로 삼아 왔고, 그래프 이론, 계산생물학, 데이터베이스 등에 쓰였다.

양측 주장은 모두 학계의 최종 검증을 받지 못했다. 성과는 이론상 계산 시간에 관한 것이어서 실제 컴퓨터의 프로그램이 곧바로 빨라지지는 않는다. 윌리엄스 교수는 이번 알고리즘이 특정 암호 체계를 직접 무력화한다는 근거는 아직 없다고 설명했다. 또 ETH를 반박했다고 해서 P 대 NP 난제가 풀린 것은 아니다.

OpenAI의 이번 발표는 수학, 컴퓨터과학, 이론물리학 난제 해결을 알리는 발표의 일부였다.