Donald Knuth veröffentlicht als Paper, wie Claude Opus 4.6 ein ungelöstes kombinatorisches Problem löste
(www-cs-faculty.stanford.edu)Kernaussagen
- Der Informatiker Donald Knuth, Autor von The Art of Computer Programming (TAOCP), hat bekannt gegeben, dass das neueste KI-Modell Claude Opus 4.6 ein ungelöstes kombinatorisches Problem gelöst hat, an dem er selbst seit mehreren Wochen arbeitete.
- Bei der Suche nach einer Zerlegung von Hamilton-Zyklen in einem gerichteten Graphen entdeckte Claude mithilfe von 31 Ausführungen von Python-Skripten und einer eigenen Feedback-Schleife eine funktionierende verallgemeinerte algorithmische Struktur.
- Knuth, der in der Vergangenheit skeptisch war und auf die Grenzen generativer KI hingewiesen hatte, bezeichnete das Ergebnis als „dramatischen Fortschritt bei automatisierter Deduktion und kreativem Problemlösen“ und deutete an, seine bisherige Sicht auf KI zu revidieren.
Vertiefte Analyse
Das gelöste Problem: Zerlegung in Hamilton-Zyklen (Hamiltonian Cycle Decomposition)
Knuth untersuchte beim Schreiben des nächsten Bandes von TAOCP ein Zerlegungsproblem in einem bestimmten gerichteten Graphen (digraph). In einem Graphen mit $m^3$ Knoten $ijk$ für $0 \le i, j, k < m$ besitzt jeder Knoten drei Kanten (arcs) zu $i+jk$, $ij+k$, $ijk+$ (wobei $i+ = (i+1) \bmod m$) gerichtete. Ziel war es, für alle Fälle mit $m > 2$ eine allgemeine Lösung (general decomposition) zu finden, die diese Kanten in drei gerichtete $m^3$-Zyklen zerlegt. Knuth hatte den Fall $m=3$ gelöst, stieß jedoch bei der Herleitung einer verallgemeinerten Formel für größere Werte auf Schwierigkeiten.
Implementierungsprinzip und technischer Hintergrund: Hybrides Reasoning und autonome Explorationsschleife
Knuths Kollege Filip Stappers gab dieses Problem in Claude Opus 4.6 ein, das neueste hybride Reasoning-Modell von Anthropic. Dabei ging er über eine einfache Anfrage hinaus und versah den Prompt mit strengen Einschränkungen, die einen agentischen Workflow erzwingen sollten.
Claude formulierte das Problem sofort mathematisch neu und schrieb ein Python-Skript (exploreXX.py), um eine Schleife zur Hypothesenprüfung zu starten. Über etwa eine Stunde hinweg führte es 31 Explorationen durch und probierte verschiedene Algorithmen aus, darunter Brute Force, Fiber Decompositions und Simulated Annealing.
Der entscheidende Wendepunkt bei der Problemlösung
Besonders bei der 25. Exploration analysierte Claude seine eigenen Grenzen und änderte die Suchrichtung: „Der Simulated-Annealing-Algorithmus kann einzelne Lösungen finden, aber keine allgemeine mathematische Struktur (general construction) liefern; daher ist ein rein mathematischer Ansatz nötig.“ Schließlich leitete Claude in der 31. Exploration auf Basis struktureller Muster aus den vorherigen Versuchen eine exakte verallgemeinerte Konstruktion her, die für ungerades $m$ funktioniert. Auf dieser Grundlage vervollständigte Knuth den mathematischen Beweis und nannte das Ergebnis „Claude-like decompositions“.
Wichtiger Code und Daten
Dies sind einige der zentralen Einschränkungen (Prompts), die Filip Stappers Claude gegeben hat, sowie ein Teil des von Claude protokollierten Selbstbewertungs-Logs.
# 1. Claude auferlegte Workflow-Einschränkungen (Schleifensteuerung und erzwungene Dokumentation)
"""
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. Claudes mathematische Neuformulierung des Problems (anfänglicher Ansatz)
"""
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. Claudes Selbstbewertung nach der 25. Exploration (Richtungswechsel)
"""
SA(Simulated Annealing) can find solutions but cannot give a general construction.
Need pure math.
"""
10 Kommentare
Die Person aus dem Lehrbuch fügt dem Lehrbuch ständig noch mehr hinzu....
(Anerkennung)
Na klar, Lehrbücher zu schreiben ist schließlich seine Aufgabe. (nickt)
Hahaha, jetzt werden Sie mit KI wohl noch mehr hinzufügen.
Also kommt von TAOCP doch noch mehr.
Er teilt genau mit, wie er KI zum Lösen eines Mathematikproblems eingesetzt hat, und schreibt dann die Arbeit mit dem von ihm entwickelten TeX ... einfach verdammt stilvoll.
Dank des Artikels habe ich zum ersten Mal von TAOCP erfahren; ich sollte es mir wohl einmal in Ruhe anschauen.
Dass er am nächsten Band von TAOCP schreibt
Dann kommt von der Reihe wohl noch mehr raus, krass.
Lebt er noch?
Sie korrigieren ja immer noch selbst ...