# 도널드 커누스(Donald Knuth), Claude Opus 4.6이 미해결 조합론 문제를 해결한 과정을 논문으로 공개

> Clean Markdown view of GeekNews topic #27176. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=27176](https://news.hada.io/topic?id=27176)
- GeekNews Markdown: [https://news.hada.io/topic/27176.md](https://news.hada.io/topic/27176.md)
- Type: news
- Author: [darjeeling](https://news.hada.io/@darjeeling)
- Published: 2026-03-04T08:18:23+09:00
- Updated: 2026-03-04T08:18:23+09:00
- Original source: [www-cs-faculty.stanford.edu](https://www-cs-faculty.stanford.edu/~knuth/papers/claude-cycles.pdf)
- Points: 38
- Comments: 10

## Summary

도널드 커누스옹께서 **Claude Opus 4.6**을 통해 자신이 풀지 못했던 조합론 문제의 일반 해를 얻었다고 발표했습니다. 방향 그래프의 해밀토니안 사이클 분해 문제를 놓고 Claude는 31회의 파이썬 탐색과 자체 피드백 루프를 거쳐, 수학적 구조를 스스로 재정의하며 일반화된 알고리즘을 도출했습니다. 커누스는 이를 “자동 연역과 창의적 탐구의 결합”으로 평가하며, 생성형 AI의 연구 도구로서의 가능성을 새롭게 인정했습니다.   
  
댓글이 너무 웃겼어요   
"교과서에 나온 분이 교과서에 뭘 자꾸 추가하시네"   
"그야 교과서를 쓰는게 그분의 역할이니까"

## Topic Body

##### 핵심 요약  
- '컴퓨터 프로그래밍의 예술(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가 기록한 자체 평가 로그의 일부입니다.  
  
```python  
# 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.  
"""

## Comments



### Comment 52320

- Author: bus710
- Created: 2026-03-04T08:42:06+09:00
- Points: 7

교과서에 나온 분이 교과서에 뭘 자꾸 추가하시네....

### Comment 52322

- Author: skshin
- Created: 2026-03-04T09:05:32+09:00
- Points: 2
- Parent comment: 52320
- Depth: 1

(인정)

### Comment 52395

- Author: dkang
- Created: 2026-03-04T21:36:31+09:00
- Points: 1
- Parent comment: 52320
- Depth: 1

그야 교과서를 쓰는게 그분의 역할이니까 (끄덕)

### Comment 52356

- Author: onestone
- Created: 2026-03-04T13:04:45+09:00
- Points: 1
- Parent comment: 52320
- Depth: 1

ㅋㅋㅋㅋㅋ 이제 AI로 더더 추가하실듯 하네요

### Comment 54039

- Author: roxie
- Created: 2026-03-28T18:13:26+09:00
- Points: 1

TAOCP 더 나오는 거였구나

### Comment 52357

- Author: kh0324
- Created: 2026-03-04T13:14:31+09:00
- Points: 1

수학문제를 풀기위해 AI를 쓰는 방법을 그대로 공유하여 자기가 만든 TeX으로 논문 작성.... 슈퍼 개간지

### Comment 52345

- Author: dolsangodkimchi
- Created: 2026-03-04T10:51:01+09:00
- Points: 1

기사덕분에 TAOCP 를 처음 알았는데 한번 천천히 봐봐야겠어요.

### Comment 52341

- Author: epdlemflaj
- Created: 2026-03-04T10:21:01+09:00
- Points: 1

TAOCP 차기 볼륨 집필이라니  
이거 시리즈 더 나오려나보군요 ㄷㄷㄷㄷ

### Comment 52339

- Author: jongyeol
- Created: 2026-03-04T09:59:42+09:00
- Points: 1

아직 살아계셨어요?

### Comment 52319

- Author: carnoxen
- Created: 2026-03-04T08:25:38+09:00
- Points: 1

지금도 정정하신 분...