[서론] 해밀턴 분해 문제가 마침내 해결되었습니다! 알고리즘의 대부로 불리는 88세의 도널드 너스 교수가 클로드 4.6과 GPT-5.4를 활용하여 홀짝 해밀턴 분해 문제를 해결한 논문을 발표했습니다. 특히 GPT-5.4는 14페이지 분량의 논문을 직접 발표하여 온라인에서 큰 화제를 모으고 있습니다.
88세 노인이 마침내 자신이 과거에 파놓은 구덩이를 메웠습니다!
3주 전, '알고리즘의 아버지'이자 최연소 튜링상 수상자인 도널드 크누스는 클로드(Claude)의 업적에 놀라움을 금치 못했습니다. 클로드 오퍼스 4.6이 오랫동안 풀리지 않았던 알고리즘 문제를 해결했기 때문입니다.
그는 논문의 맨 처음 부분에서 " 충격적이야! 충격적이야 !"라고 외쳤다.
논문 링크: https://cs.stanford.edu/~knuth/papers/claude-cycles.pdf
하지만 추가 연구를 통해 실제로 유사한 분해 방법이 760개나 존재하며, 클로드는 그중 하나만을 발견했다는 사실이 밝혀졌습니다.
이는 m이 홀수인 "요새"만을 정복했을 뿐이며, m이 짝수인 경우에는 아직 보편적인 해결책이 없다 .
업데이트된 논문은 이 문제 해결에 상당한 진전이 이루어졌음을 보여줍니다!
GPT-5.4 Pro는 Claude의 역할을 이어받아 모든 짝수 m≥8에 대해 14페이지 분량의 보고서를 직접 출력하고, 계산을 통해 m=2000까지의 경우를 검증합니다.
또한 GPT와 Claude가 협력한 결과, 다중 에이전트 워크플로우를 통해 홀수와 짝수 m을 구성하는 더 간단한 방법이 발견되었습니다.
일부 사람들은 Lean 언어를 사용하여 홀수 경우에 대한 Claude의 증명을 형식화하기도 했습니다.
이로써 해밀턴 분해 문제는 완전히 해결되었다.
Claude 4.6에서 GPT-5.4에 이르기까지, 그리고 수많은 업계 리더들의 공동 노력 덕분에 수십 년간의 난관이 마침내 해결되었습니다.
논문의 마지막 부분에서 노인은 감정에 북받쳐 이렇게 말했다.
우리는 참으로 흥미로운 시대에 살고 있습니다. 포스가 당신과 함께하길.
88세의 알고리즘 개척자는 거대한 함정을 파놓았다.
조합론에서 해밀턴 경로는 언제나 방어하기는 쉽지만 공격하기는 어려운 요새와 같았습니다.
간단히 말해, 복잡한 그래프 네트워크에서 다른 노드를 반복하지 않고 모든 노드를 통과하는 닫힌 루프를 찾는 것입니다.
반면 해밀턴 분해 문제는 그래프를 여러 개의 순환으로 완벽하게 분해하는 것을 목표로 합니다. 이는 단순히 계산 복잡성의 문제일 뿐만 아니라 수학적 구성 능력에 대한 극한의 시험이기도 합니다.
이 구덩이는 크누스가 직접 판 것이다.
컴퓨터 과학에 관한 그의 대표작인 '컴퓨터 프로그래밍의 기술(TAOCP)'을 집필하는 동안, 해밀턴 분해는 항상 그가 염두에 두었던 "임시방편"이었다.
이 문제는 수십 년 동안 해결되지 않았으며, 기술적인 용어로 설명하면 다음과 같습니다.
이전에는 학계에서 홀수와 짝수 모두를 포괄하는 완전한 해결책을 제시하지 못했습니다.
노드 수가 증가함에 따라 검색 공간은 기하급수적으로 팽창하며, 인간의 뇌는 이러한 심오한 어둠 앞에서 생리적으로 무력감을 느끼는 경우가 많습니다.
지난 30년 동안 수많은 천재들이 그 공백을 메우려고 노력했지만, 대부분은 "모든 해법이 홀수이거나 짝수여야 한다"는 최후의 방어선에서 실패했습니다.
2026년 봄까지 크누스는 다른 무기로 바꾸기로 결정했습니다.
m이 짝수일 경우에도 해법이 있을까요?
클로드 작품 4.6의 마지막 버전에서, 31번의 탐색 끝에 마침내 간단한 규칙 세트가 제시되었습니다.
s = (i + j + k) mod m
s, i, j의 조건을 바탕으로 다음 규칙에 따라 i를 증가시킬지, j를 증가시킬지, k를 증가시킬지 결정합니다.
s=0이면 이동 방향은 j 값에 따라 결정됩니다. 0<s <m−1이면 이동 방향은 i 값에 따라 결정됩니다. s=m−1이면 다른 규칙이 적용됩니다.
그 결과, 클로드는 프로그램을 통해 m=3, 5, 7, 9, 11일 때 경로가 유효함을 확인했습니다.
보시다시피, 클로드는 m이 홀수인 경우만 해결했으며, m이 짝수인 경우에 대한 진정한 해법은 아직 찾지 못했습니다.
3월 3일, 필립 스태퍼스는 그 노인에게 "이 이야기에는 더 많은 내용이 있습니다."라고 편지를 썼습니다.
스테이퍼스는 짝수 m에 대해 클로드 오푸스 4.6을 다시 사용했고, 약 4시간의 계산 끝에 마침내 어느 정도 진전을 이루었지만 완전한 해결책은 찾지 못했습니다.
궁극적으로 클로드는 특이한 경우와 유사한 지역 섬유 구조를 구축한 다음 검색을 실행하여 이를 개선했습니다.
마지막 단계에서는 실제 건설 방법을 찾는 것보다 "검색 속도를 높이는 데" 대부분의 시간을 소비했습니다.
이 시스템은 시뮬레이티드 어닐링 또는 백트래킹 알고리즘을 사용하여 해결책을 찾으려고 시도하면서 여러 프로그램을 실행했습니다.
스테이퍼스의 제안에 따라 클로드는 문제를 해결하기 위해 ORTools CP-SAT(구글의 오픈 소스 툴킷의 일부이며 AddCircuit 제약 조건을 포함함)를 사용하라는 지시를 받았고, 기적이 일어났습니다.
최신 프로그램은 단 몇 초 만에 결과를 낼 수 있습니다!
그러던 중 3월 4일, 싱가포르에 사는 친구 호 분 수안으로부터 더욱 충격적인 소식을 전해 들었다.
그는 gpt-5.3-codex를 사용하여 짝수 m≥8의 분해를 성공적으로 구현하는 코드를 생성했습니다.
신뢰성을 검증하기 위해 그는 8에서 200 사이의 모든 짝수 m과 400에서 2000 사이의 임의의 짝수 몇 개를 테스트했고, 결과는 모두 정상이었다.
m=2000일 경우, 80억 개의 정점을 가진 거대한 그래프 구조가 된다는 점을 명심하세요!
만약 그것이 순전히 인간의 노력에 의한 것이라면, 수동 계산을 통해 그 정확성을 증명하는 것은 완전히 허황된 꿈일 것이다.
거의 동시에 린(Lean) 커뮤니티의 킴 모리슨이 매우 신속하게 행동에 나섰습니다.
그는 클로드의 해석이 옳다는 자신의 기존 증명을 공식화하고 검증한 후, 3월 4일에 곧바로 온라인에 게시했습니다.
수학 천재들이 연구 분야에 한데 모였다
"Exocija"라는 가명을 사용하는 또 다른 익명의 연구원은 홀수 m에 대해 작동하는 새로운 구조를 발견했습니다.
순전히 계산적인 관점에서 보면, 이는 현재 이용 가능한 가장 간단한 해결책일 가능성이 높지만, 그 증명 과정은 가장 간단하지 않을 수도 있습니다.
C 프로그래밍에서 효과적인 코드 분해는 특정 코드 몇 줄을 매우 간결한 논리 코드로 바꾸는 것만으로도 달성할 수 있습니다.
게다가 거의 모든 단계에서 "012"라는 식별자 치환을 교묘하게 활용합니다.
- 만약 (s == 0)이면 d = (j == m - 1 ? "201" : "021");
- 그렇지 않고 s가 m - 1이면 d = (j == 0 ? "102" : "120")입니다.
- 그렇지 않으면 d = "012";
그는 어떻게 해냈을까요? 답은 바로 모델 간 협업입니다.
엑소시야는 최상위 모델인 GPT-5.4와 클로드 4.6 소네트 사이에 텍스트를 반복적으로 붙여넣으며, 각 모델의 서로 다른 사고 방식을 활용하여 서로에게 영감을 불어넣었고, 마침내 완전한 증명을 완성해냈다.
수정 사항 없음, 14페이지 분량의 논문이 GPT-5.4에서 직접 출력되었습니다.
짝수 m의 구성에 관한 진정한 클라이맥스는 아직 오지 않았다.
gpt-5.3-codex가 생성한 알고리즘이 너무 복잡하기 때문에 Ho Boon Suan은 GPT-5.4 Pro에 최종 지침을 내리기로 결정했습니다.
여러분의 과제는 앞서 제시된 알고리즘이 m이 8 이상의 짝수일 때 항상 길이가 m³인 세 개의 반복문을 생성한다는 것을 엄밀하게 증명하는 것입니다.
이 알고리즘이 작동하는 원리를 자세히 설명하고 더 간단한 구성 방법이 있는지 살펴보는 것이 가장 좋을 것입니다.
GPT-5.4 Pro가 이처럼 놀라운 결과를 낼 줄 누가 알았겠는가?
훌륭한 형식과 논리적 타당성을 갖춘 14페이지 분량의 학술 논문.
"요약"부터 "결론"까지, 구조가 완벽하고 매끄러운 전환을 보여줍니다.
더욱이, 이 언어는 TeX 표준을 사용하는데, TeX의 창시자는 바로 크누스입니다. AI는 이 언어를 통해 그에게 경의를 표하는 듯합니다.
무엇보다 중요한 것은, 해당 논문이 린(Lean) 방식의 형식 검증 도구를 통과했다는 점입니다.
호의 말에 따르면, 이는 GPT-5.4 Pro 단독으로 이뤄낸 위업이었으며, 심지어 문장 부호 하나도 수정할 필요가 없었다고 합니다!
이는 그 논리적 연쇄가 수학적 의미에서 "절대적 진리"임을 의미합니다.
AI가 "자기 자신과 싸운다"는 사실을 Claude+GPT가 마침내 완벽하게 증명했습니다.
이 이야기의 절정은 케스톤 아퀴노-마이클스입니다.
이 방법은 m이 홀수인 경우에 대한 효율적인 분해법을 제공할 뿐만 아니라, m이 짝수인 경우에 대해서도 기존 방법보다 훨씬 간단한 우아한 분해법을 제공합니다.
게다가 그는 크누스가 이전에 간과했던 관련 참고 자료(즉, 아래 이미지의 마지막 참고 자료)도 발견했습니다.
논문 사전 공개본: https://arxiv.org/abs/2203.11017
무엇보다도 주목할 만한 점은 그가 이러한 협력적 상호작용 모델을 면밀히 분석했다는 것인데, 이는 미래에 발생할 새로운 문제들을 해결하고 대처하는 방식에 상당한 시사점을 줄 수 있다.
- 전체 보고서: https://github.com/no-way-labs/residue/blob/main/paper/completing_claudes_cycles.pdf
- 오픈 소스 프로젝트: https://github.com/no-way-labs/residue
- 간단히 말해, 케스턴 아퀴노-마이클스는 단순히 AI에게 질문만 한 것이 아니라, 독창적인 "협업 워크플로"를 구축했습니다.
이것은 탄소 기반 시스템과 실리콘 기반 시스템을 아우르는 협력적인 활동에 더 가깝고, 클로드, GPT, 그리고 인류 간의 긴밀한 협력이라고 할 수 있습니다.
두 에이전트는 동일한 "잔여물" 프롬프트를 사용하여 독립적으로 실행됩니다.
두 에이전트가 사용하는 구조화된 탐색 단서 단어
하지만 각자는 자신의 강점을 활용할 수 있습니다.
에이전트 O: 홀수 번째 경우를 5번의 탐색으로 해결 (기호적 증명)
에이전트 C: m=4, 6, 8, 10, 12에 대한 구체적인 해답(데이터)을 찾으세요.
하지만 두 에이전트는 직접 통신하지 않고, 오케스트레이터를 통해 통신합니다. 데이터와 도구는 사령관(인간이 조종하는 Opus 4.6)을 통해 전송됩니다.
조정자는 "언제, 무엇을, 어떤 형식으로 전송할지"를 결정해야 하는데, 이는 두 담당자만으로는 수행할 수 없습니다.
예를 들어, 에이전트 O는 짝수 경우 m=10에서 멈춰서 더 이상 진행할 수 없습니다. 이때 오케스트레이터는 에이전트 C의 해결책을 에이전트 O에게 전달합니다. 에이전트 O는 해결책을 받자마자 "배치 레이어"의 m-2개 레이어와 "복구 레이어"의 2개 레이어로 구성된 패턴을 즉시 식별합니다.
결국, 수십 년 동안 인류를 당혹스럽게 했던 "홀수와 짝수 문제에 대한 완벽한 해결책"은 두 인공지능 에이전트 간의 치열한 경쟁 끝에 완전히 풀렸다.
인간은 전장을 규정하고, 기계는 심연을 채운다.
이러한 "격차 해소"는 과학 연구 패러다임의 완전한 전환을 의미합니다.
과학자의 역할이 바뀌었습니다. 예를 들어, 크누스는 더 이상 종이에 코드 한 줄 한 줄을 계산하는 장인이 아닙니다. 그는 문제의 범위를 정의하고, 검증 논리를 설계한 다음, 인공지능이 시행착오의 블랙홀을 메우도록 지시합니다.
연구 패러다임이 바뀌었습니다. 과거에는 인간이 경계를 설정했지만, 이제는 AI가 그 공백을 채우고 있습니다.
수학자에게 가장 가치 있는 능력은 더 이상 해시레이트 아니라 "질문을 던지는 직관"과 "답을 검증하는 미적 감각"이다.
인공지능은 끝없는 시행착오를 통해 최적의 경로를 찾아내는 역할을 하고, 인간은 최종적으로 그 결과가 우리가 찾고자 하는 진실인지 확인하는 역할을 합니다.
다음은 누구일까요?
88세의 알고리즘 전문가조차 인공지능을 활용하여 부족한 부분을 메우기 시작한다면, 수학 연구 방식이 돌이킬 수 없는 변화를 겪고 있음을 깨달아야 합니다.
이는 크누스에게만 승리가 아니라, 인간 지능의 "치트 코드 업그레이드"와도 같은 의미를 지닌다.
"기계들이 서로 싸우는" 시대에, 가장 엄격한 수학 분야조차 인공지능에게 문을 열었습니다.
만약 당신이 여전히 "인공지능이 나를 대체할까?"라고 고민하고 있다면, 이미 차세대 "지능형 설계자"가 될 기회를 놓쳤을지도 모릅니다.
인공지능이 해결해야 할 다음 세기의 난제는 리만 가설일까요, 아니면 물리학의 통일장론일까요?
이 "극도로 흥미로운 시대"에서 우리가 유일하게 두려워해야 할 것은 진화의 속도를 무시하는 것입니다.
참고 자료:
https://x.com/slow_developer/status/2038399555490791765
https://x.com/mubeitech/status/2038388810157826467
https://x.com/BoWang87/status/2037648937453232504
이 글은 위챗 공식 계정 "뉴 인텔리전스" 에서 KingHZ Peach가 작성하고 36Kr의 허가를 받아 게시한 글입니다.
