도널드 커누스(Donald Knuth), Claude Opus 4.6이 미해결 조합론 문제를 해결한 과정을 논문으로 공개
(www-cs-faculty.stanford.edu)핵심 요약
- '컴퓨터 프로그래밍의 예술(TAOCP)'의 저자인 컴퓨터 과학자 도널드 커누스가 최신 AI 모델 'Claude Opus 4.6'이 자신이 수 주간 연구하던 미해결 조합론 문제를 해결했다고 발표했습니다.
- 방향 그래프의 해밀토니안 사이클 분해능을 찾는 문제에서, Claude는 31번의 Python 스크립트 실행과 자체 피드백 루프를 통해 작동하는 일반화된 알고리즘 구조를 발견했습니다.
- 과거 생성형 AI의 한계를 지적하며 회의적이었던 커누스는 이번 결과를 "자동 연역과 창의적 문제 해결의 극적인 진전"으로 평가하며 AI에 대한 기존 견해를 수정할 것임을 시사했습니다.
심층 분석
해결한 문제: 해밀토니안 사이클 분해 (Hamiltonian Cycle Decomposition)
커누스는 TAOCP의 차기 볼륨을 집필하면서 특정 방향 그래프(digraph)에서의 분해 문제를 연구 중이었습니다. 정점 $0 \le i, j, k < m$인 $m^3$개의 정점 $ijk$를 가진 그래프에서 각 정점은 $i+jk$, $ij+k$, $ijk+$ (단, $i+ = (i+1) \bmod m$)로 향하는 3개의 호(arcs)를 갖습니다. 목표는 $m > 2$인 모든 경우에 대해 이 호들을 3개의 방향성 $m^3$-사이클로 분해하는 일반적인 해(general decomposition)를 찾는 것이었습니다. 커누스는 $m=3$인 경우는 해결했으나, 그 이상의 일반화 공식 도출에는 난항을 겪고 있었습니다.
구현 원리 및 기술적 배경: 하이브리드 추론과 자율 탐색 루프
커누스의 동료인 Filip Stappers는 Anthropic의 최신 하이브리드 추론 모델인 'Claude Opus 4.6'에 이 문제를 입력했습니다. 이때 단순 질의를 넘어, 에이전트적(Agentic) 워크플로우를 강제하는 강력한 제약 조건을 프롬프트로 부여했습니다.
Claude는 즉시 문제를 수학적으로 재정의하고 파이썬 스크립트(exploreXX.py)를 작성하여 가설 검증 루프를 시작했습니다. 약 1시간 동안 브루트 포스(Brute force), 파이버 분해(fiber decompositions), 시뮬레이티드 어닐링(Simulated Annealing) 등 다양한 알고리즘을 시도하며 31번의 탐색을 수행했습니다.
문제 해결의 핵심 분기점
특히 25번째 탐색에서 Claude는 "시뮬레이티드 어닐링 알고리즘은 개별 해를 찾을 수는 있지만, 일반적인 수학적 구조(general construction)를 제시할 수 없으므로 순수 수학적 접근이 필요하다"고 스스로의 한계를 분석하고 탐색 방향을 전환했습니다. 결국 31번째 탐색에서 과거 탐색의 구조적 패턴을 바탕으로 $m$이 홀수일 때 동작하는 정확한 일반화 구조를 도출해 냈습니다. 커누스는 이 결과를 바탕으로 수학적 증명을 완료하고, 이를 '클로드형 분해(Claude-like decompositions)'로 명명했습니다.
주요 코드 및 데이터
Filip Stappers가 Claude에게 부여한 핵심 제약 조건(프롬프트)과, Claude가 기록한 자체 평가 로그의 일부입니다.
# 1. Claude에게 부여된 워크플로우 제약 (루프 제어 및 문서화 강제)
"""
After EVERY exploreXX.py run, IMMEDIATELY update this file [plan.md] before doing anything else.
No exceptions. Do not start the next exploration until the previous one is documented here.
"""
# 2. Claude의 수학적 문제 재정의 (초기 접근)
"""
Need sigma: Z3 m — S3, assigning a permutation of {0,1,2} at each vertex;
cycle c at vertex v goes in direction sigma(v)[c].
Each resulting functional digraph must be a single Hamiltonian cycle.
"""
# 3. 25번째 탐색 후 Claude의 자체 평가 (방향성 전환)
"""
SA(Simulated Annealing) can find solutions but cannot give a general construction.
Need pure math.
"""