New lower bounds for the degree/diameter problem via interaction with a browser-accessible LLM

Das große Ganze: Ein mathematisches Rätsel und ein digitaler Partner

Stellen Sie sich ein riesiges Puzzle vor, das den Namen Degree/Diameter Problem (Grad/Durchmesser-Problem) trägt. Das Ziel ist es, die größtmögliche „Stadt“ (ein Netzwerk aus Punkten und Linien) zu bauen, bei der zwei Regeln strikt befolgt werden:

1. Die Grad-Regel: Jedes Gebäude (Punkt) darf höchstens eine bestimmte Anzahl an Straßen (Linien) haben, die mit ihm verbunden sind.
2. Die Durchmesser-Regel: Egal, welche zwei Gebäude man auswählt, man muss in der Lage sein, von einem zum anderen in einer sehr geringen Anzahl von Schritten zu gelangen (nicht mehr als 5 Schritte).

Mathematiker versuchen seit Jahrzehnten, die größten möglichen Städte zu bauen, die diesen Regeln folgen. Je größer die Stadt, desto besser die Punktzahl.

Der Durchbruch:
Diese Arbeit berichtet, dass ein Forscher, der allein mit einem Standard-Webbrowser und einem KI-Chatbot (ChatGPT) arbeitete, zwei neue „Städte“ gebaut hat, die signifikant größer sind als alle bisher bekannten.

• Stadt A: Ein Netzwerk mit 34.992 Gebäuden.
• Stadt B: Ein Netzwerk mit 147.456 Gebäuden.

Beide Städte folgen der Regel, dass man jeden Ort in 5 Schritten oder weniger erreichen kann, und kein Gebäude hat mehr als 12 bzw. 16 Straßen. Diese Zahlen schlagen die bisherigen Weltrekorde.

Wie sie es geschafft haben: Der „Controller“ und die „Faser“

Das Geheimnis beim Bau dieser massiven Städte war nicht bloßes Raten. Der Forscher und die KI entdeckten einen cleveren Weg, das Problem in zwei kleinere, handhabbare Teile zu zerlegen. Stellen Sie sich das wie den Bau einer riesigen Hotelkette vor:

1. Der Controller (Der Bauplan): Stellen Sie sich eine kleine, einfache Karte mit einigen zentralen Knotenpunkten vor. Dies ist der „Controller“. Seine Aufgabe ist es, die allgemeine Richtung vorzugeben. In diesem Fall fand die KI eine kleine Karte mit 144 Knotenpunkten, die sicherstellt, dass man von jedem Knotenpunkt zu jedem anderen genau in 5 Schritten gelangen kann, ohne jemals sofort umzukehren (ein „Nicht-Rückverfolgung-Spaziergang“).
2. Die Faser (Die Zimmer): Stellen Sie sich nun vor, dass an jedem einzelnen Knotenpunkt auf dieser kleinen Karte nicht nur ein Gebäude steht. Stattdessen haben Sie dort einen massiven, komplexen Turm aus Zimmern. Dies ist die „Faser“. Die KI entwickelte ein mathematisches „Aufzugsystem“ (unter Verwendung von Algebra und endlichen Körpern), das genau vorgibt, wie man sich zwischen den Zimmern in diesen Türmen bewegt, basierend darauf, welche Straße man nimmt.

Der magische Trick:
Die Genialität der Entdeckung lag in der Erkenntnis: Wenn man die kleine Karte (den Controller) richtig hinbekommt und das Aufzugsystem (die Faser) richtig gestaltet, kann man beides kombinieren, um eine riesige Stadt zu erschaffen. Die kleine Karte regelt die Navigation im „großen Ganzen“, und das Aufzugssystem regelt die „feinen Details“ der Bewegung zwischen Millionen spezifischer Punkte.

Die Mensch-KI-Kollaboration: Ein Tanz der Führung

Diese Arbeit ist einzigartig, weil sie nicht behauptet, dass die KI die Mathematik allein gelöst hat, noch dass der Mensch sie allein gelöst hat. Sie beschreibt eine spezifische Art des Zusammenwirkens:

• Kein Super-System: Der Forscher baute keinen komplexen Roboter oder eine spezialisierte Software-Engine. Er nutzte einfach die Standard-ChatGPT-Website, wie jeder andere auch.
• Der Mensch als Kapitän: Der Forscher agierte wie ein Kapitän eines Schiffes. Er sagte der KI nicht, wie sie den Aufzug bauen oder wie die Karte aussehen sollte. Stattdessen gab er Anweisungen auf hoher Ebene, wie zum Beispiel:
  • „Kopiere nicht einfach alte Ideen.“
  • „Wenn wir in einer Sackgasse stecken, halte inne und überdenke die gesamte Strategie.“
  • „Gib mir einen Grund zu glauben, dass diese neue Idee funktionieren wird, bevor wir versuchen, sie aufzubauen.“
• Die KI als Entdeckerin: Die KI erkundete tausende mathematische Möglichkeiten. Sie probierte viele Ideen aus, die scheiterten. Wenn sie feststeckte, sagte der menschliche Kapitän: „Stopp, dieser Pfad ist eine Sackgasse. Versuche einen anderen Winkel.“

Der „Aha!“-Moment:
Lange Zeit versuchte die KI, kleine Fehler in schlechten Designs zu beheben (wie das Flicken eines lecken Bootes). Der menschliche Kapitän stoppte dies und verlangte nach einem „neuen Prinzip“. Die KI schlug daraufhin die Controller/Fiber-Idee (den „Routenplan-Aufzug“) vor. Dies war der Moment, in dem die Abstraktion erschien. Sob es dieses neue Prinzip gab, ging es nur noch um die Verfeinerung der Details, um die Rekorde zu brechen.

Was diese Arbeit nicht behauptet

Es ist wichtig, sich an das zu halten, was die Arbeit tatsächlich aussagt:

• Es ist kein allgemeiner Beweis dafür, dass KI alle mathematischen Probleme lösen kann. Dies war ein spezifischer Fallbericht.
• Es geht nicht um medizinische oder klinische Anwendungen. Dies ist reine Graphentheorie (Mathematik).
• Es geht nicht darum, dass die KI die fertige Arbeit schreibt. Der menschliche Forscher hat jeden Schritt überprüft, die Beweise formuliert und die Verantwortung für das Endergebnis übernommen. Die KI war ein Werkzeug zur Entdeckung, nicht der Autor.

Zusammenfassung

Betrachten Sie diese Arbeit als das Logbuch einer erfolgreichen Expedition. Ein menschlicher Entdecker nutzte einen digitalen Kompass (die KI), um durch einen mathematischen Dschungel zu navigieren. Der Entdecker ließ den Kompass nicht das Auto fahren; er steuerte ihn, sagte ihm, wann er anhalten sollte, und fragte ihn nach neuen Routen. Gemeinsam fanden sie einen Pfad zu einer massiven, zuvor unentdeckten mathematischen Struktur und bewiesen damit, dass selbst eine handelsübliche, browserbasierte KI – wenn sie von einem Menschen mit einer klaren Strategie geleitet wird – dabei helfen kann, Weltrekorde in der reinen Mathematik zu brechen.