Claudes Zyklen [PDF]

 (www-cs-faculty.stanford.edu)
4 Punkte von GN⁺ 2026-03-04 | 1 Kommentare | Auf WhatsApp teilen
  • Anthropics Modell Claude Opus 4.6 löste Donald Knuths Problem der Zerlegung gerichteter Hamiltonkreise, an dem er mehrere Wochen geforscht hatte
  • Das Problem besteht darin, für einen gerichteten Graphen mit (m^3) Knoten eine Zerlegung in drei Hamiltonkreise zu finden; Claude löste es vollständig für ungerades m
  • Claude führte schrittweise verschiedene Suchstrategien aus, darunter „Faser“-Zerlegung, 3D-Serpentinenmuster, Tiefensuche (DFS) und Simulated Annealing
  • Am Ende leitete Claude eine allgemeine Lösung in Form eines Python-Programms her, die Filip Stappers für ungerade m von 3 bis 101 verifizierte und dabei die vollständige Zerlegung bestätigte
  • Knuth bewertet das Ergebnis als bahnbrechenden Fortschritt bei automatischem Schlussfolgern und kreativem Problemlösen und stellt klar, dass der Fall gerader m weiterhin ungelöst ist

Hintergrund und Definition des Problems

  • Das Forschungsthema betrifft gerichtete Hamiltonkreise (directed Hamiltonian cycles) und soll in einem künftigen Band von Knuths The Art of Computer Programming erscheinen
  • Der Graph besteht aus (m^3) Knoten (ijk), und von jedem Knoten gehen drei Kanten aus: (i+jk), (ij+k), (ijk+)
  • Das Ziel ist, für alle (m>2) eine allgemeine Lösung zu finden, die diese Kanten in drei gerichtete (m^3)-Kreise zerlegt

Claudes Suchprozess

  • Claude Opus 4.6 ist Anthropics Hybrid-Reasoning-Modell; Filip Stappers stellte das Problem vor und wies es an, den Fortschritt zu dokumentieren
  • In der Anfangsphase formulierte Claude das Problem als funktionalen Graphen und Permutationszuweisungsproblem um und versuchte lineare sowie quadratische funktionale Ansätze, die jedoch scheiterten
  • Danach testete es nacheinander DFS-Suche, Analyse von 2D-Serpentinenmustern und 3D-Gray-Code-basierte Muster
  • Anschließend führte es den Ansatz der „Faser“-Zerlegung ein, analysierte die nach (s = (i+j+k) \mod m) geschichtete Struktur und fand mit Simulated Annealing (SA) partielle Lösungen

Entdeckung und Verifikation der Lösung

  • Im 31. Suchschritt erzeugte Claude ein Python-Programm, das nur von einer einzelnen Koordinatenregel pro Faser abhängt
  • Dieses Programm erzeugte für m=3,5,7,9,11 jeweils vollständige drei Hamiltonkreise
  • Filip Stappers testete dies für alle ungeraden m von 3 bis 101 und bestätigte die vollständige Zerlegung
  • Knuth vereinfachte dies zu C-Code und bewies mathematisch, dass jeder Kreis tatsächlich die Länge (m^3) hat

Verallgemeinerung und mathematische Analyse

  • Es wurde bestätigt, dass sich einige der Hamiltonkreise für (m=3) auf alle ungeraden m verallgemeinern lassen
    • Bei (m=3) lassen sich von 11.502 Kreisen 1.012 auf (m=5) verallgemeinern, und 996 sogar bis (m=7)
    • Diese 996 lassen sich auf alle ungeraden m>1 verallgemeinern
  • Eine „Claude-like“-Zerlegung wird durch einfache Regeln definiert, die nur von den Randwerten von i, j und s (0 oder m−1) abhängen
  • Satz: Damit eine „Claude-like“-Zerlegung für alle ungeraden m>1 gültig ist, müssen die drei Kreise bei m=3 verallgemeinerbare Hamiltonkreise sein
  • Rechnerisch wurde ermittelt, dass 760 Claude-like-Zerlegungen für alle ungeraden m gültig sind

Ungelöster Fall gerader m und Fazit

  • Für gerade m bleibt der Fall weiterhin offen (open)
    • Für (m=2) wurde in früheren Arbeiten die Unmöglichkeit bewiesen
    • Claude fand für (m=4,6,8) partielle Lösungen, scheiterte jedoch an einer Verallgemeinerung
  • Bei der Suche nach geraden m zeigte Claude Fehler und anomales Verhalten, worauf die Suche abgebrochen wurde
  • Knuth bewertet dies als historische Leistung des KI-basierten automatischen Schlussfolgerns und merkt an, dass es ein Fortschritt sei, der dem Namen Claude Shannon gerecht werde

Anhang: Regeln der beiden anderen Kreise

  • Zweiter Kreis (c=1):
    • Wenn (s=0), dann j erhöhen; wenn (0<s<m−1), dann i erhöhen; wenn (s=m−1), dann bei i>0 k erhöhen, bei i=0 j erhöhen
  • Dritter Kreis (c=2):
    • Bei (s=0): wenn j<m−1, dann i erhöhen, bei j=m−1 k erhöhen
    • Bei (0<s<m−1): wenn i<m−1, dann k erhöhen, bei i=m−1 j erhöhen
    • Bei (s=m−1): i erhöhen
  • Die Reihenfolge der Knoten bei s=0 für jeden Kreis ist explizit angegeben; damit lässt sich die Struktur des gesamten Kreises beweisen

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2026-03-04
Hacker-News-Kommentare

  • Es ist interessant, über Problemfelder nachzudenken, auf die sich RL-Skalierung anwenden lässt.
    Früher war man auf menschliche Kognition angewiesen, aber jetzt sind solche Muster in Wahrscheinlichkeitsverteilungen eingebettet und damit für alle zugänglich.
    Fraglich ist allerdings, ob Modelle mithalten können, wenn sich die Grenzen der Wissenschaft immer weiter verschieben.
    Damit Anthropic Claude im Jahr 2030 aktuell halten kann, bräuchte es entweder (a) kontinuierliches Lernen für ein festes Modell oder (b) fortlaufendes Training – beides ist nicht einfach.

    • Open-Weights-Modelle sind eine Art Zeitkapsel.
      Nach dem Zeitpunkt des Knowledge Cutoff bleiben sie dort für immer stehen.
    • Wenn Datenteilung erlaubt wäre, könnten die Inference-Ergebnisse von heute zu den Trainingsdaten von morgen werden.
      Man könnte sich auch ein Modell vorstellen, das Forschenden kostenlose Inference bietet und dafür ihren Denkprozess (Trace) als Trainingsdaten nutzt.
    • Wenn man hört, was Forschende zuletzt sagen, scheint sich die Modellarchitektur künftig in Richtung stark erweiterter Context Windows zu entwickeln.
      Modelle wie Qwen3-next, Qwen3.5 und Nemotron 3 Nano unterstützen mit Hybrid Attention Millionen-Token-Fenster bei geringeren Speicherkosten.
    • Der Großteil von Forschung und Lernen läuft bereits über LLMs und Coding Agents.
      Echtzeit-Feedback-Schleifen durch menschliche Verifikation, Code-Ausführung und Suche wirken als Trainingssignal für Modelle.
    • Im Jahr 2030 hält vielleicht eher Claude Anthropic auf dem neuesten Stand.
      Halb als Witz gemeint, aber völlig unmöglich ist es nicht.

  • Das erinnert an das frühere Gespräch zwischen Wolfram und Knuth über GPT-4.
    Knuth war damals skeptisch, aber nach Modellen wie Opus 4.6 scheint seine Haltung weicher geworden zu sein.
    Es ist bewundernswert, seine Meinung angesichts neuer Belege zu ändern.
    Das zugehörige Gespräch gibt es hier.

    • Das Aktualisieren der Prior-Wahrscheinlichkeit anhand neuer Evidenz ist genau der Reiz der bayesianischen Statistik.
      Das ist auch der Kern wissenschaftlichen Denkens.

  • Ich finde, die Einleitung von Knuths Text ist etwas missverständlich.
    Es wirkt fast so, als hätte Claude das Problem direkt gelöst, tatsächlich hat Claude aber ein Beispiel erzeugt, das Knuth dann verallgemeinert und zu einem Beweis ausgearbeitet hat.

    • Ich habe mit Claude selbst ähnliche Experimente gemacht, und die Synergie zwischen Mensch und LLM ist wirklich groß.
      LLMs sind schwach darin, die Richtung vorzugeben, aber wenn die Richtung einmal feststeht, sind sie gut in tiefgehender Exploration.
      Lässt man sie allein, gehen sie oft in seltsame Richtungen, aber mit menschlicher Führung sind sie hervorragende Partner.
    • Ich glaube nicht, dass Knuth es überbewertet hat.
      Claude hat die Kernidee durchdrungen, und der Mensch hat sie nur noch ausgearbeitet.
    • Man kann auch sagen, dass Claude die von Knuth gemeinte „Lösung“ geliefert hat.
      Das formale Aufräumen des Beweises ist nur Nebenarbeit.
    • Die Fähigkeit, zu früheren Versuchen zurückzukehren und zu reflektieren und zu korrigieren, wirkt eindeutig wie ein Zeichen von Intelligenz.

  • Interessant fand ich die Stelle, dass Claude beim geraden Fall steckenblieb.
    Vermutlich wurde entweder claude.ai oder claude code verwendet, und es ist in eine Context-Overflow-Zone (dumb zone) geraten.

    • Es wäre gut, diese dumb zone visualisieren zu können.
      So etwas wie ein Graph zur Context-Auslastung wie bei Copilot, damit Nutzer das bemerken können, wäre nützlich.
    • Letztlich werden die Ergebnisse chaotisch, wenn man kein Context Compacting macht.
    • Die Erwähnung eines „plan document“ klingt so, als sei ein Dokument zur Sitzungsverwaltung verwendet worden.
    • Manche fragten sich auch, was diese dumb zone überhaupt ist.

  • Jemand hat Claude das von Arthur C. Clarke bekannt gemachte Pentomino-Puzzle lösen lassen.
    Als Board und Teile mit 64-Bit-Integern dargestellt wurden, schrieb es ein C#-Programm und löste es schnell, lieferte im 20x3-Fall aber wegen einer falschen Zuordnung eine falsche Antwort.
    Interessant, weil es wie ein typisch menschlicher Fehler wirkt.

  • Kurz gesagt: Knuth stellte das Problem vor, und ein Freund führte mit Claude rund 30 Explorationsläufe durch.
    Claude erstellte ein Python-Programm, das die ungeraden Fälle löste, und Knuth bewies dann diesen Ansatz.
    Die geraden Fälle bleiben weiterhin ein ungelöstes Problem.

    • Allerdings wirkt Knuths Formulierung „careful human guidance“ etwas übertrieben.
      Tatsächlich blieb Claude oft hängen oder machte Fehler, sodass Menschen es nur gelegentlich erinnern mussten.
    • Was Knuth hervorhob, war wohl, dass der formale Beweis weiterhin Sache des Menschen ist.
      Von wem die Kernidee ursprünglich kam, bleibt unklar.

  • Es ist gerade wirklich eine spannende Zeit, sich mit ungelösten Problemen zu befassen.
    Ich würde gern Forschung von vor zehn Jahren noch einmal gemeinsam mit Claude erkunden.

  • Die Stärken von LLMs scheinen drei Dinge zu sein: riesiges Wissen, Fähigkeit, Verbindungen herzustellen, und unermüdliches Trial-and-Error.
    Wenn diese drei Dinge zusammenkommen, entstehen manchmal erstaunliche Ergebnisse.
    Vielleicht liegt selbst ein Beweis für P≠NP in einem schwachen Verbindungsglied, das Menschen bisher übersehen haben.

    • Der letzte Punkt ist möglicherweise weniger eine Eigenschaft des LLM selbst als vielmehr eine des Agent Loop.
      Das LLM ist darin nur eine Komponente.
    • Trotzdem ist unermüdliche iterative Exploration ein großer Vorteil gegenüber Menschen.
      Wenn sonst alles gleich ist, ist das der entscheidende Unterschied.
    • Der Aussage, dass aus der Kombination der drei Dinge großartige Resultate entstehen, stimme ich voll zu.
    • Gleichzeitig ist es beängstigend, dass solche Fähigkeiten auch für Überwachungssysteme eingesetzt werden könnten.
    • Mit „Fähigkeit, Verbindungen herzustellen“ sind wohl in Wirklichkeit Verbindungen gemeint, die in den Trainingsdaten bereits existieren.
      Ganz neue Verbindungen zu schaffen, ist noch immer schwierig.

  • Ich frage mich, ob die Aussage „LLMs sind nur Maschinen zur Vorhersage des nächsten Wortes“ wirklich zutrifft.
    Wie ließe sich sonst solches Problemlösen erklären? Ist das Denken?

    • Wenn man perfekt vorhersagen könnte, welches Wort Einstein als Nächstes sagen würde, hätte man damit bereits Intelligenz implementiert.
      Die Formulierung „das wahrscheinlichste Wort“ ist eine zu starke Vereinfachung.
    • Diese Erklärung passt auf Basismodelle, aber Modelle wie Opus 4.6 haben zusätzlich RLHF und weiteres Training darübergelegt.
      Letztlich könnte die „Fähigkeit, gut vorherzusagen, was als Nächstes passiert“ selbst eine Definition von Intelligenz sein.
    • Basismodelle lernen beim Erkennen des Web-Musters „Answer:“ ganz natürlich auch Muster des Problemlösens.
      Dank RLHF werden nicht bloß Vorhersagen, sondern hilfreiche Antworten belohnt.
      Deshalb tauchen Ausdrücke wie „delve“ übermäßig oft auf.
      Siehe dazu das Dokument AI SIGNS.
    • Im Kern werden also weiterhin Wörter aus einer Wahrscheinlichkeitsverteilung gezogen, aber genau diese Verteilung ist der Kern von Intelligenz.
      LLMs lernen eben diese Verteilung.
    • Wenn der einfache Mechanismus „das wahrscheinlichste Wort“ mit dem gesamten Wissen der Menschheit kombiniert wird, entsteht daraus enorme Kraft.
      Das als bloße Simplifizierung spöttisch abzutun, verfehlt das Wesen der Technologie.

  • Interessant, dass es sich um einen Bericht von Knuth selbst handelt.
    Zeit, ihn einmal ohne Hilfe eines LLM direkt zu lesen und zu verstehen.

    • Mir fehlte die Zeit, also habe ich stattdessen einen von jemandem erstellten Zusammenfassungslink gesucht.