앤스로픽, 클로드가 ETH 반박 알고리즘 찾았다고 발표

앤스로픽이 자사 인공지능 모델 클로드가 계산복잡도 이론의 핵심 가설인 지수시간 가설(ETH)을 반박하는 결과를 찾아냈다고 27일 발표했다. 회사 측에 따르면 이번 발견은 지난 10월 16일 이뤄졌다.

앤스로픽 연구원 레벤트 알푀게는 X에 올린 글에서 내부 연구용 클로드 모델이 10월 16일 인간의 개입 없이 핵심 알고리즘을 찾아냈다고 밝혔다. 앤스로픽은 이 과정에서 생성된 출력이 총 1400만 토큰에 달했다고 전했다. 이번 발표는 오픈AI가 수학과 컴퓨터과학의 난제에서 유사한 결과를 알린 지 약 6시간 뒤에 나왔다.

앤스로픽은 논문 'Subexponential-time algorithms for 3-SAT'와 린(Lean) 검증 코드를 깃허브에 공개했다. 논문 저자로는 사람이 아닌 'Claude (Anthropic)'이 표기됐다. 제안된 알고리즘은 3-SAT 문제를 준지수 시간에 푸는 방식으로, ETH의 전제와 충돌한다.

오픈AI 역시 자사 모델이 10월 16일 ETH를 반박하는 증명을 찾아냈고 다음 날 린으로 이를 검증했다고 밝혔다. 두 회사는 같은 날 서로 다른 세부 접근법으로 유사한 결론에 독립적으로 도달했다는 설명이다. 다만 이번 결과는 이론에 관한 것으로, 실제 프로그램이 곧바로 빨라진다는 뜻은 아니다.

ETH는 1999년 알고리즘의 한계를 분석하는 핵심 근거로 제시된 이후 그래프 이론과 계산 생물학, 데이터베이스 등 여러 분야에 활용돼 왔다. 오픈AI에 따르면 이 가설에 기대고 있는 연구 결과가 다수 존재한다. 양사가 내놓은 주장은 아직 학계의 최종 검증을 거치지 않았다.