GPT-5.6 und Fable haben sich zusammengeschlossen, um ein seit 25 Jahren ungelöstes mathematisches Problem zu lösen.

GPT-5.6 und Fable 5 haben sich zusammengetan, um ein seit 25 Jahren offenes mathematisches Problem zu lösen.

Dimitris Papailiopoulos, leitender Forscher bei Microsoft Research, hat einen polynomiellen Zeitalgorithmus bewiesen, der die MIMO-Erkennung exakt auf die Maximum-Likelihood-Schwelle bringt.

Der Autor gibt an, dass dieser Prozess ihn ganze sieben Tage gekostet hat.

Die MIMO-Erkennung ist ein klassisches Problem im Bereich der drahtlosen Kommunikation, bei dem das Empfangsgerät die ursprünglich vom Sendegerät gesendeten Informationen vollständig aus dem durch Rauschen gestörten Signal wiederherstellen muss.

Statistisch gesehen ist diese Operation bereits durchführbar, aber die bisherigen Methoden basieren auf einer erschöpfenden Suche, deren Zeitaufwand exponentiell ist.

Daher stellt sich die Frage, ob die Wiederherstellung ohne erschöpfende Suche mithilfe schneller Algorithmen erreicht werden kann.

Im Jahr 2001 glaubten Hassibi und Vikalo, einen Durchbruch gefunden zu haben, aber im Jahr 2005 wurde dieser Weg von Jaldén und Ottersten als nicht gangbar nachgewiesen.

Anschließend hat die akademische Welt nacheinander Methoden wie Semidefinite Relaxation, lokale Suche mit Bit-Umschaltung, AMP und statistisch-physikalische Methoden ausprobiert, wobei das beste Ergebnis nur bei dem doppelten Wert der theoretischen Schwelle liegen konnte.

25 Jahre lang sind Generationen von Wissenschaftlern nacheinander angetreten, aber niemand konnte dieses Problem lösen.

25 Jahre lang war nur eine erschöpfende Suche möglich

Die MIMO-Erkennung ist ein grundlegendes Problem in der drahtlosen Kommunikation.

Das Sendegerät sendet N Bits über einen N×N-Kanal, der diese Bits miteinander vermischt und zusätzlich Rauschen überlagert;

Das Empfangsgerät verfügt nur über ein gestörtes Signal und muss die ursprünglich vom Sendegerät gesendeten N Bits fehlerfrei wiederfinden.

Theoretisch gibt es eine narrensichere Methode namens Maximum-Likelihood-Erkennung, bei der alle möglichen Bit-Kombinationen berechnet werden, um diejenige zu finden, die am besten zum empfangenen Signal passt.

Diese Methode findet garantiert die richtige Antwort – vorausgesetzt, man ist bereit zu warten: N Bits bedeuten 2^N Kombinationen, und bei einem etwas größeren N würde die erschöpfende Suche ewig dauern.

1989 bewies Sergio Verdú, dass dieses Problem im schlimmsten Fall NP-schwer ist, das heißt, unabhängig vom verwendeten Algorithmus gibt es bestimmte Eingaben, bei denen der Rechenaufwand exponentiell explodiert.

Aber der „schlimmste Fall“ bezieht sich auf mathematisch absichtlich konstruierte Kanalmatrizen, die speziell dafür entwickelt wurden, Algorithmen zu behindern.

Reale drahtlose Kanäle werden nicht absichtlich konstruiert: Jede Dämpfung und jedes Rauschen entsteht zufällig, und sie wählen nicht die schwierigsten Fälle aus, um das Empfangsgerät zu behindern.

Daher stellte die akademische Welt seit Anfang der 2000er Jahre eine konkretere Frage –

Wenn der Kanal zufällig erzeugt wird und statistisch die Möglichkeit besteht, die ursprünglichen Bits wiederherzustellen, lässt sich dann zwangsläufig ein Algorithmus finden, der keine erschöpfende Suche erfordert?

Spätere Studien ergaben eine genaue Trennlinie: Wenn das Signal-Rausch-Verhältnis 2logN erreicht, nähert sich die Wahrscheinlichkeit, dass die gesendeten Bits vollständig wiederhergestellt werden können, 1 an.

Unterhalb dieser Linie beginnt selbst die Maximum-Likelihood-Erkennung Fehler zu machen, daher wird diese Trennlinie als Maximum-Likelihood-Schwelle bezeichnet.

Das Problem wird also konkret: Lässt sich ein schneller Algorithmus entwerfen, der exakt die Maximum-Likelihood-Schwelle erreicht?

Im Jahr 2001 glaubten Babak Hassibi und Haris Vikalo, die Antwort gefunden zu haben.

Sie analysierten einen Algorithmus namens Sphärendecodierer (sphere decoder).

Dieser Algorithmus zeichnet zunächst eine „Kugel“ um das empfangene Signal, sucht nur unter den Kandidaten innerhalb der Kugel und überspringt die außerhalb liegenden direkt, um so den Suchbereich zu komprimieren.

Hassibi und Vikalo leiteten die Formel für den erwarteten Komplexitätsgrad dieses Algorithmus ab, die wie eine polynomielle Zeit aussah.

Wenn diese Schlussfolgerung gültig wäre, wäre das Problem im Wesentlichen gelöst.

Aber im Jahr 2005 widerlegten Joakim Jaldén und Björn Ottersten diese Schlussfolgerung.

Sie bewiesen, dass der erwartete Komplexitätsgrad des Sphärendecodierers bei jedem festen Signal-Rausch-Verhältnis tatsächlich exponentiell und nicht polynomiell ist.

Der Grund dafür ist, dass der Radius der Kugel mit der Problemgröße zunehmen muss, um das gesendete Signal mit einer nicht gegen Null gehenden Wahrscheinlichkeit in die „Kugel“ einzuschließen. Sobald die Kugel größer wird, steigt die Anzahl der zu durchsuchenden Kandidaten innerhalb der Kugel ebenfalls exponentiell an.

Nachdem der Weg des Sphärendecodierers nicht gangbar war, wandte sich die akademische Welt verschiedenen Näherungsverfahren zu: Semidefinite Relaxation, lokale Suche mit Bit-Umschaltung, AMP (approximate message passing) und Methoden aus der statistischen Physik.

Jede dieser Methoden lieferte eine überzeugende Analyse, aber keine wurde nachgewiesen, dass sie exakt die Schwelle von 2logN erreicht.

Im Jahr 2020 erzielte eine Methode namens box relaxation, die diskrete Probleme zu kontinuierlichen Optimierungsproblemen entspannt, das damals beste streng bewiesene Ergebnis: Sie konnte eine exakte Wiederherstellung erreichen, wenn das Signal-Rausch-Verhältnis 4logN erreichte, aber die Komplexität lag immer noch beim Doppelten der theoretischen Schwelle.

25 Jahre lang klaffte diese Lücke zwischen der statistischen „Möglichkeit der Wiederherstellung“ und der „Möglichkeit der Wiederherstellung mit schnellen Algorithmen“.

Letzte Woche wurde diese Lücke geschlossen.

Dimitris Papailiopoulos bewies zusammen mit GPT-5.6 und Claude Fable 5, dass ein einfacher Algorithmus mit nur zwei Schritten ebenfalls alle Bits exakt wiederherstellen kann, wenn das Signal-Rausch-Verhältnis gleich 2logN ist, und zwar in polynomieller Zeit mit nur O(N³) Operationen.

Außerdem ist das in diesem Papier bewiesene Ergebnis zweiseitig.

Auf der einen Seite wird bewiesen, dass dieser Algorithmus das Signal exakt wiederherstellen kann, wenn das Signal-Rausch-Verhältnis gleich 2logN ist; auf der anderen Seite wird weiter bewiesen, dass sogar die „einfache“ Maximum-Likelihood-Erkennung zu scheitern beginnt, sobald das Signal-Rausch-Verhältnis geringfügig unter die Maximum-Likelihood-Schwelle von 2logN fällt.

Gemeinsamer Beweis von GPT-5.6 und Fable 5

Dimitris bat GPT-5.6 und Fable 5, dieses Problem zu versuchen. Die beiden Modelle gaben schnell jeweils ihre eigenen Beweisideen an, aber der anschließende Verfeinerungsprozess verlief mit vielen Hindernissen.

Der Ansatz von GPT-5.6 verwendete einen Algorithmus namens AMP, ein Werkzeug, dessen Analysemethoden Dimitris bisher nicht vollständig verstanden hatte.

Fable 5 lieferte einen anderen Ansatz, der auf „Sign-LMMSE plus gierige bitweise Umschaltung“ basiert – ein alter Algorithmus, der in der Branche praktisch verwendet wird, aber nie streng bewiesen wurde.

Beide Ansätze lieferten vollständige Beweise, die behaupteten, eine exakte Wiederherstellung bei einem Signal-Rausch-Verhältnis von 2logN zu erreichen.

Dimitris wählte schließlich den von Fable vorgeschlagenen Weg und ließ GPT die darin enthaltenen Lücken prüfen und beheben.

GPT reparierte die Lücken, aber der fertige Beweis war eine „Symbolmauer“: Variablen verwiesen auf andere Variablen, die wiederum auf noch mehr Variablen verwiesen, und er war voll von Matrixanalyse-Werkzeugen, die Dimitris nicht verstand.

In den folgenden Tagen bat er die beiden Modelle wiederholt, die Argumente des jeweils anderen zu vereinfachen, mit der einzigen Bedingung, dass die Schwelle von 2logN in jeder vereinfachten Version erhalten bleiben musste.

Darüber hinaus durfte er beliebige Änderungen vornehmen, solange er sie selbst verstehen konnte.

Er lehnte außerdem eine formale Verifikation mit Lean ab – der Grund war sehr einfach: Er beherrschte Lean nicht.

Lean ist ein Werkzeug, mit dem Computer automatisch prüfen können, ob ein mathematischer Beweis gültig ist. Um es zu verwenden, muss der Beweis jedoch zuerst in eine formale Sprache übersetzt werden, die Lean versteht.

Diese Übersetzungsarbeit selbst kann fehlerhaft sein, und da Dimitris Lean nicht beherrscht, kann er nicht prüfen, ob die Übersetzung korrekt ist.

Nach einer Woche voller Arbeit erhielt er endlich einen Beweis, der Zeile für Zeile manuell nachgerechnet und überprüft werden kann.

Im Kern besteht dieser Algorithmus aus nur zwei Schritten.