GPT-5.6 widerlegt eine fast 30-jährige mathematische Vermutung, der gesamte Dialog ist öffentlich: Der Prompt umfasst nur 58 Wörter???

Schon wieder so etwas??? GPT-5.6 hat in letzter Zeit eine wahre Flut von Gegenbeispielen in der Mathematik aufgedeckt...

Die fast 30 Jahre alte Dinitz-Garg-Goemans-Vermutung im Bereich der Graphentheorie wurde gerade von GPT-5.6 Pro durch ein Gegenbeispiel widerlegt.

Ein Forscher namens Dmitry Rybin nutzte für den gesamten Argumentationsprozess insgesamt nur 4 Prompts mit zusammen 58 englischen Wörtern.

Keine Tausende Wörter umfassende Prompt-Engineering, keine komplizierten Formeln, der gesamte Inhalt lautet im Grunde nur:

Forsche weiter, suche weiter, gib mir ein vollständiges Gegenbeispiel!!!

Nach solchen schrittweisen Aufforderungen lieferte GPT-5.6 Pro tatsächlich ein überraschendes Ergebnis —

Die Dinitz-Garg-Goemans-Vermutung ist falsch.

Was die KI schließlich lieferte, umfasste nicht nur ein Schaubild, sondern auch vier Seiten mit Beweiszertifikaten, ein genaues erschöpfendes Überprüfungsprogramm, maschinenlesbare Gegenbeispieldaten und den LaTeX-Quellcode.

Und dann wurde diese fast 30 Jahre alte mathematische Vermutung einfach durch ein paar „Dringlichkeitsaufforderungen“ zu einem fatalen Bug getrieben???

Fast 30 Jahre alte Vermutung, von GPT-5.6 Pro um einen fatalen Bug widerlegt

Lassen Sie uns zuerst klären, worum es bei dieser langnamigen Dinitz-Garg-Goemans-Vermutung eigentlich geht.

Wir können sie direkt als „Lieferproblem“ vorstellen.

Angenommen, ein Lager soll Waren an mehrere Zielorte liefern. Wenn Aufteilung erlaubt ist, kann dieselbe Warencharge auf mehrere Routen verteilt werden —

Die Hälfte fährt auf der Autobahn, die andere Hälfte auf der Landstraße, solange am Ende alles zugestellt wird, ist das in Ordnung~

Aber unter der Regel der nicht aufteilbaren Lieferung muss jede Warencharge vollständig eine einzige Route nehmen, sie darf nicht aufgeteilt werden!!!

Tatsächlich kommt diese Situation in der Realität nicht selten vor, zum Beispiel bei Netzwerkdaten, Logistikaufträgen, Verkehrssteuerung und Lieferkettenverteilung treten ähnliche Probleme auf:

Die mathematische optimale Lösung kann Aufgaben in unzählige kleine Teile zerlegen, aber ein Fahrzeug oder ein Auftrag in der Realität kann nicht in 0,37 Teile zerschnitten werden.

△

Sobald die Aufteilung verboten ist, lässt sich die ursprüngliche optimale Lösung kaum direkt übernehmen.

Die Waren, die früher auf mehrere Wege verteilt waren, müssen jetzt als ganze Charge in eine bestimmte Route eingefahren werden, sodass die Belastung einiger Straßen plötzlich stark ansteigen kann.

Das eigentliche Problem, das gelöst werden muss, lautet also:

Wie kann man eine Lösung, bei der „Waren aufgeteilt transportiert werden dürfen“, in eine Version umwandeln, bei der „jede Charge als Ganzes transportiert werden muss“, ohne dass die Straßen übermäßig überlastet werden?

1999 veröffentlichten Yefim Dinitz, Naveen Garg und Michel Goemans ein klassisches Papier zum Bereich der nicht aufteilbaren Lieferung aus einer einzigen Quelle und bewiesen, dass diese Überlastung innerhalb eines bestimmten Rahmens kontrolliert werden kann.

Aber nachdem die Frage „Wird die Überlastung zu stark?“ gelöst wurde, gibt es noch ein anderes praktisches Problem: Wird es teurer?

Daraufhin stellte der bekannte Wissenschaftler für kombinatorische Optimierung Goemans eine stärkere Version mit Kosten auf —

Unter Beibehaltung der oben genannten Obergrenze für Überlastung sollen die Gesamtkosten auch nicht höher sein als die der ursprünglichen Lösung mit aufteilbaren Lieferungen.

Einfach ausgedrückt: Wenn man durch aufgeteilten Transport sowohl günstig als auch wenig überlastet fahren kann, sollte man theoretisch auch dann eine gleichermaßen günstige Lösung finden, die höchstens um eine Charge mehr Überlastung verursacht, wenn jede Warencharge vollständig eine einzige Route nehmen muss.

Diese intuitiv sehr einleuchtende Vermutung wurde jedoch für allgemeine Graphenstrukturen nie bewiesen, nachfolgende Forschungen erzielten Ergebnisse nur für einige Sonderfälle.

Jahrelang blieb diese Vermutung danach weder bewiesen noch widerlegt.

Das von GPT-5.6 Pro vorgelegte Gegenbeispiel erfüllt genau die zwei Bedingungen der Vermutung nicht, die gleichzeitig erfüllt sein sollen:

Es darf weder zu stark überlastet noch zu teuer werden.

Es konstruiert einen kleinen Graphen mit nur 7 Knoten und 9 gerichteten Kanten, der einen gemeinsamen Startpunkt und drei Zielorte hat, wobei die Nachfrage der drei Warenchargen jeweils 15, 10 und 15 beträgt:

Jede Warencharge hat zwei wählbare Routen:

Eine Route ist teurer, jeder Auftrag kostet 30 bei der Durchfahrt; die andere Route kostet 0, muss aber mit anderen Aufträgen einige Straßenabschnitte teilen.

Wenn Aufteilung erlaubt ist, können Teile der drei Warenchargen die kostenpflichtige Route und Teile die kostenlose Route nehmen, sodass die Gesamtkosten 58 betragen.

Aber! Sobald gefordert wird, dass jede Warencharge vollständig eine einzige Route wählen muss, tauchen Schwierigkeiten auf...

Das von GPT-5.6 Pro gezogene Ergebnis lautet, dass die drei kostenlosen Optionen tatsächlich paarweise miteinander in Konflikt stehen!

Wenn zwei beliebige Chargen gleichzeitig die kostenlose Route wählen, fahren sie gemeinsam in denselben Straßenabschnitt, sodass die tatsächliche Belastung 25, 30 oder 40 erreicht; die zulässige Obergrenze der entsprechenden Straßen beträgt nur 24, 29 oder 39.

Jedes Mal übersteigt der Wert genau um eine Einheit.

Um die von der Vermutung festgelegte Belastungsobergrenze einzuhalten, kann also höchstens eine der drei Warenchargen die kostenlose Route nehmen.

Die restlichen zwei Chargen müssen die kostenpflichtige Route wählen.

Jede Charge kostet 30, zusammen für zwei Chargen beträgt das Mindestkosten jeder Lösung, die die Belastungsanforderungen erfüllt, mindestens 60.

Das führt zu einer Situation, in der beide Bedingungen nicht gleichzeitig erfüllt werden können: Wenn die Straßenbelastung innerhalb des vorgeschriebenen Bereichs gehalten werden soll, betragen die Mindestkosten 60; wenn die Kosten auf das ursprüngliche Niveau von 58 gedrückt werden sollen, wird mindestens eine Straße die Obergrenze überschreiten.

Aber die Vermutung geht genau davon aus, dass beide Bedingungen gleichzeitig erfüllt werden können.

Außerdem ist die Überprüfung dieses Gegenbeispiels nicht so kompliziert wie man denkt.

Jeder der drei Zielorte hat zwei Routen, insgesamt gibt es nur 2^3=8 Kombinationen.

Wenn man alle 8 Möglichkeiten nacheinander auflistet, stellt man fest, dass 4 davon die Kapazitätsanforderungen erfüllen und Kosten von 90, 60, 60 und 60 haben; die anderen 4 sind zwar günstiger, führen aber alle zu Straßenüberlastungen.

Alle Fälle können durch erschöpfende Prüfung überprüft werden, es gibt keine fehlenden versteckten Routen.

Das heißt, solange die Definition dieses Graphen vollständig mit den Bedingungen der ursprünglichen Vermutung übereinstimmt, reicht diese Lücke von zwei Einheiten zwischen 58 und 60 aus, um die Vermutung zu widerlegen.

Vier Runden intensiver Aufforderungen, die GPT-5.6 zwingen, das Gegenbeispiel zu liefern

Das Interessanteste an dieser Sache verbirgt sich tatsächlich im öffentlichen Dialog zwischen Rybin und GPT-5.6 Pro.

Wenn man sieht, dass eine seit fast 30 Jahren offene mathematische Vermutung von einer KI widerlegt wird, nimmt man instinktiv an, dass dahinter eine ganze Reihe von superkomplexen Prompts nacheinander zum Einsatz gekommen sein müssen!!!

Tatsächlich hat man sich da aber geirrt.

Denn die erste Anfrage, die Rybin an GPT-5.6 Pro stellte, enthielt außer der angehängten Datei wirklich nur sehr einfache, klare Alltagsprache:

Ja, so schlicht und einfach.

Daraufhin begann GPT-5.6 Pro, den Anweisungen zu folgen und eifrig zu arbeiten.

Es erstellte zuerst ein Überprüfungsverfahren für lineare Programmierung, probierte dann verschiedene Strukturen wie Hyperwürfel, geschichtete Graphen und Zusammenführungs-Verzweigungsnetzwerke aus und durchsuchte Tausende von kleinen Instanzen.

Nach dieser intensiven Suche lautete die erste Antwort des Modells jedoch: Kein gültiges Gegenbeispiel gefunden. (doge)

Sogar GPT-5.6 Pro wies ausdrücklich darauf hin, dass man zu einem falschen mathematischen Ergebnis kommen würde, wenn man die gefundene ungefähre Konstruktion als Gegenbeispiel ausgibt.

Übersetzt bedeutet das: Ich habe mein Bestes gegeben, diese Aufgabe kann im Moment wirklich nicht gelöst werden!!!

Unser Protagonist Rybin akzeptierte das nicht. Er fügte keine neuen Formeln hinzu und wies auch keine Details an, sondern antwortete nur kurz:

Forsche weiter und finde ein vollständiges, bedingungsloses Gegenbeispiel~

Daraufhin durchsuchte GPT-5.6 Pro das Problem noch einmal intensiv, aber auch die zweite Runde scheiterte.

Rybin forderte es weiter auf, basierend auf dem tiefen Verständnis der Problemstruktur zuerst eine klare Strategie zu entwickeln und dann weiter zu suchen.

In der dritten Runde hatte das Modell den Suchbereich auf eine Routing-Struktur mit nur 24 Zuständen eingegrenzt, die Lösung schien zum Greifen nah.

Aber die KI konnte immer noch kein vollständiges Gegenbeispiel liefern...

Zu diesem Zeitpunkt gab Rybin den vierten Prompt aus: Es gibt bereits zu viele Teilergebnisse, lass uns die Sache mit einem vollständigen, bedingungslosen Gegenbeispiel abschließen.

Nun, die Anweisung war so deutlich formuliert.

Dieses Mal lieferte GPT-5.6 Pro endlich das Gegenbeispiel-Graph mit 7 Knoten und 9 gerichteten Kanten — insgesamt vier Prompts mit zusammen 58 englischen Wörtern.

Keine Tausende Wörter umfassende Rollenbeschreibung, keine Dutzende von umständlichen Regeln, der gesamte Inhalt lässt sich im Grunde zusammenfassen als:

Ich drücke nach! Ich drücke weiter! Ich drücke noch mehr!