클로드의 순환들 [PDF]

3 weeks ago 11

Anthropic의 모델 Claude Opus 4.6이 Donald Knuth가 몇 주간 연구하던 방향성 해밀토니안 순환 분해 문제를 해결함
문제는 (m^3)개의 꼭짓점을 가진 방향 그래프의 세 개의 해밀토니안 순환으로의 분해를 찾는 것이며, Claude는 이를 odd m(홀수 m) 에 대해 완전하게 해결함
Claude는 “섬유(fiber) 분해”, “3D 뱀형(serpentine) 패턴”, 심층 탐색(DFS), 시뮬레이티드 어닐링 등 다양한 탐색 전략을 단계적으로 수행함
최종적으로 Python 프로그램 형태의 일반 해법을 도출하고, Filip Stappers가 m=3부터 101까지의 홀수 m에 대해 검증하여 완전한 분해를 확인함
Knuth는 이 결과를 자동 추론과 창의적 문제 해결의 획기적 진전으로 평가하며, 짝수 m의 경우는 여전히 미해결로 남아 있음을 명시함

문제의 배경과 정의

연구 주제는 방향성 해밀토니안 순환(directed Hamiltonian cycles) 에 관한 것으로, Knuth의 저서 The Art of Computer Programming의 향후 권에 포함될 예정
그래프는 (m^3)개의 꼭짓점 (ijk)로 구성되며, 각 꼭짓점에서 세 개의 간선이 존재: (i+jk), (ij+k), (ijk+)
목표는 모든 (m>2)에 대해 이 간선들을 세 개의 방향성 (m^3)-순환으로 분해하는 일반 해법을 찾는 것

Claude Opus 4.6은 Anthropic의 혼합 추론(hybrid reasoning) 모델로, Filip Stappers가 문제를 제시하고 진행 과정을 문서화하도록 지시함
초기 단계에서 Claude는 문제를 함수적 그래프와 순열 할당 문제로 재정의하고, 선형 및 2차 함수형 접근을 시도했으나 실패
이후 DFS 탐색, 2D 뱀형 패턴 분석, 3D Gray 코드 기반 패턴 등을 차례로 실험
“섬유(fiber) 분해” 접근을 도입하여, (s = (i+j+k) \mod m)을 기준으로 층화된 구조를 분석하고, 시뮬레이티드 어닐링(SA) 을 통해 부분적 해를 발견

(m=3)의 해밀토니안 순환 중 일부가 모든 홀수 m에 대해 일반화 가능함을 확인
- (m=3)에서 11,502개의 순환 중 1,012개가 (m=5)로 일반화되고, 996개는 (m=7)까지 일반화됨
- 이 996개는 모든 홀수 m>1에 대해 일반화 가능
“Claude-like” 분해는 i, j, s의 경계값(0 또는 m−1) 에만 의존하는 단순 규칙으로 정의됨
정리: “Claude-like” 분해가 모든 홀수 m>1에서 유효하려면, m=3에서의 세 순환이 일반화 가능한 해밀토니안 순환이어야 함
계산 결과, 760개의 Claude-like 분해가 모든 홀수 m에서 유효함

짝수 m의 경우는 여전히 미해결(open) 상태
- (m=2)는 불가능함이 기존 연구에서 증명됨
- Claude는 (m=4,6,8)에서 부분적 해를 찾았으나 일반화 실패
Claude는 짝수 m 탐색 중 오류와 비정상 동작을 보여 탐색이 중단됨
Knuth는 이를 AI 기반 자동 추론의 역사적 성취로 평가하며, Claude Shannon의 이름에 걸맞은 진보라고 언급

두 번째 순환(c=1):
- (s=0)이면 j 증가, (0<s<m−1)이면 i 증가, (s=m−1)일 때 i>0이면 k 증가, i=0이면 j 증가
세 번째 순환(c=2):
- (s=0)에서 j<m−1이면 i 증가, j=m−1이면 k 증가
- (0<s<m−1)에서 i<m−1이면 k 증가, i=m−1이면 j 증가
- (s=m−1)이면 i 증가
각 순환의 s=0에서의 꼭짓점 순서가 명시되어 있으며, 이를 통해 전체 순환의 구조를 증명 가능