KI widerlegt 27 Jahre alte Informatik-Vermutung – das Urteil der Experten steht noch aus

Worum es geht

Ende Oktober hat OpenAI behauptet, ein internes KI-Modell habe die Exponential Time Hypothesis (ETH) widerlegt. Das ist eine 27 Jahre alte Vermutung, auf der Hunderte Arbeiten der theoretischen Informatik aufbauen. Das 67-seitige Paper trägt den knappen Titel „The Exponential Time Hypothesis is False“. Einen Tag später zog Anthropic mit einem eigenen, unabhängigen Gegenbeweis nach. Beide Firmen haben ihre Beweise in Lean geprüft, einem Programm, das mathematische Beweise Zeile für Zeile auf logische Fehler kontrolliert. Paper und Formalisierungen liegen öffentlich auf GitHub.

Fast zwei Wochen danach fehlt aber noch das entscheidende Urteil der Fachleute. Laut einem Bericht von shiftdelete.net haben die drei Forscher, die die Prüfung leiten, sich noch nicht festgelegt. Einer von ihnen ist Russell Impagliazzo, der die Vermutung 1999 selbst mit aufgestellt hat. Er nannte die Nachricht gegenüber der New York Times einen „Schock“.

Was die Exponential Time Hypothesis besagt

Die ETH stammt von Russell Impagliazzo und Ramamohan Paturi, beide an der UC San Diego, zusammen mit Francis Zane. Sie dreht sich um 3-SAT, ein klassisches Logikrätsel. Man hat viele Ja/Nein-Schalter und Regeln, die jeweils drei davon verknüpfen. Gesucht ist eine Schalterstellung, die alle Regeln gleichzeitig erfüllt. Eine vorgeschlagene Lösung zu prüfen ist leicht. Eine zu finden ist schwer, denn mit jedem zusätzlichen Schalter verdoppelt sich die Zahl der möglichen Kombinationen.

Die ETH behauptet, dass es keine wesentliche Abkürzung gibt. Im schlimmsten Fall soll jeder Algorithmus eine Rechenzeit brauchen, die exponentiell mit der Zahl der Variablen wächst, also so ähnlich wie beim Durchprobieren aller Möglichkeiten. Forscher nutzten die ETH wie eine tragende Wand. Laut OpenAI stützen sich Hunderte Arbeiten aus Graphentheorie, Computerbiologie, Datenbanken und Geometrie darauf, um zu zeigen, dass bestimmte Probleme nicht schnell lösbar sind. Fällt die Wand, wackeln diese unteren Schranken, also Beweise der Form „schneller als X geht es nicht“.

Was OpenAI und Anthropic genau behaupten

OpenAI beschreibt einen deterministischen Algorithmus, der ohne Zufall arbeitet. Er zählt alle erfüllenden Belegungen einer k-CNF-Formel, einer Verallgemeinerung von 3-SAT, und zwar in subexponentieller Zeit: Der Aufwand wächst langsamer als jede Exponentialfunktion. Dabei braucht er nur polynomiell viel Speicher. Weil Zählen mindestens so schwer ist wie die bloße Frage, ob es überhaupt eine Lösung gibt, wäre damit auch die ETH-Schranke für 3-SAT gebrochen. Laut Yahoo/BeInCrypto braucht der Algorithmus für n Variablen grob 2^(n/√log n) Schritte.

Die zeitliche Abfolge nach Angaben von OpenAI:

Anthropic schreibt das eigene Paper Claude zu. Laut dem zugehörigen Repository hat eine interne Forschungsversion den Algorithmus gefunden. Das Repository weist auch darauf hin, dass es nur um asymptotisches Verhalten geht und nicht darum, Formeln in der Praxis schneller zu lösen.

OpenAI meldete am selben Tag zwei weitere Durchbrüche. Laut The Next Web haben seine Modelle die Local-Smoothing-Vermutung von Christopher Sogge aus dem Jahr 1991 in allen Dimensionen bewiesen. Damit wären auch die Kakeya- und die Stein'sche Restriktionsvermutung erledigt. In der Physik will OpenAI rigoros gezeigt haben, dass bestimmte Quantenfeldtheorien in vier Dimensionen existieren, darunter die reine Yang-Mills-Theorie. Sie ist Teil eines der Millennium-Probleme des Clay Mathematics Institute. Diese Arbeit prüft eine Gruppe um den Nobelpreisträger David Gross. Sie will das KI-Material vorerst nicht veröffentlichen und die Arbeit selbst aufschreiben.

Wie weit die Prüfung ist

Der Stand der Prüfung ist gemischt. Freiwillige haben die Lean-Beweise beider Labore mit unabhängigen Prüfprogrammen erneut durchlaufen lassen. Laut shiftdelete hatte aber keines der beiden Labore den Schritt formalisiert, der vom eigenen Maschinenmodell auf ein Standardmodell überträgt. Ein Maschinenmodell ist die genaue mathematische Definition dessen, was ein „Rechenschritt“ ist. Diese Lücke haben externe Forscher zwischen dem 2. und 5. November in Lean geschlossen.

Offen ist der menschliche Teil. Impagliazzo, Paturi und Ryan Williams vom MIT organisieren eine öffentliche Prüfung. Sie müssen sich darauf einigen, ob die formalen Definitionen wirklich der Lehrbuchversion der ETH entsprechen. Außerdem müssen sie die schärfere Schranke im OpenAI-Paper prüfen, die nicht vollständig formalisiert wurde. In einem offenen Brief stellen die drei klar:

„Unsere Beteiligung sollte nicht als Bestätigung der Behauptung verstanden werden. Ein Ergebnis dieser Tragweite erfordert sorgfältige, unabhängige Prüfung.“

Laut Williams bekommen die Prüfer kein Geld und haben keine Verschwiegenheitsvereinbarungen unterschrieben. Auf ihren Wunsch hat OpenAI zugesagt, alle Rohdaten zum ETH-Ergebnis freizugeben und eine Fachkonferenz zu finanzieren. Impagliazzo sagte der Zeitschrift Science: „Für mich ist das nicht zu 100 Prozent sicher.“ Die meisten Forscher hätten erwartet, dass zuerst strengere Varianten der Hypothese fallen. Der Informatiker Scott Aaronson schrieb in seinem Blog, seine Studenten seien in sein Büro gekommen, um ihm zu sagen, dass ein OpenAI-Modell die ETH widerlegt habe.

Werden Computer jetzt schneller – und ist Verschlüsselung in Gefahr?

Kurzfristig nicht. Die ETH ist eine asymptotische Aussage, sie betrifft also das Verhalten bei beliebig großen Eingaben. Eine Widerlegung muss deshalb nur bei unvorstellbar großen Problemen besser abschneiden. Schätzungen von außen zufolge zeigt sich der Vorteil der geprüften Schranke von OpenAI erst ab etwa 10 hoch 2.389 Variablen. Ein Problem dieser Größe ließe sich niemals speichern. Für SAT-Solver im Chipdesign oder in der Logistik ändert sich nichts. OpenAI schreibt selbst, dass es noch viel Forschung braucht, um nützliche Algorithmen zu finden und die Theorie in praktische Vorteile umzusetzen. Die New York Times zeigt sich in ihrer Überschrift optimistischer: Das Ergebnis könne „eines Tages“ Chipdesign beschleunigen und Verschlüsselung knacken. Das ist eine ferne Möglichkeit und keine Folge des aktuellen Beweises.

Wichtig ist auch die Abgrenzung zu P vs. NP. Diese große offene Frage lautet, ob jedes Problem, dessen Lösung sich schnell prüfen lässt, auch schnell lösbar ist. Die ETH war eine strengere Behauptung als P ≠ NP. Ihr Fall lässt die große Frage deshalb offen. OpenAI-Präsident Greg Brockman schrieb kurz nach der Ankündigung: „P ist wahrscheinlich immer noch nicht gleich NP.“ Bei Yahoo/BeInCrypto heißt es dazu bildhaft, die KI habe einen kürzeren Weg über den Bergkamm gefunden und keinen Tunnel hindurch. Bitcoin-Signaturen beruhen auf Elliptische-Kurven-Kryptografie, und dieses Problem behandelt der Algorithmus gar nicht. Für Belustigung sorgte nebenbei das Kürzel: Auf X witzelten Nutzer über einen Kurssturz von „$ETH“, obwohl die Vermutung nichts mit Ethereum zu tun hat.

Wer bekommt die Anerkennung?

OpenAI sagt, es beanspruche keinen wissenschaftlichen Verdienst. Die Anerkennung sollen die Forscher bekommen, die die Ergebnisse erklären und aufschreiben. Zusätzlich gab die Firma 5 Millionen Dollar an die Simons Foundation für Workshops und Konferenzen, die KI-Ergebnisse prüfen und weiterentwickeln. Impagliazzo, Paturi und Williams fragen in ihrem Brief trotzdem, wie Anerkennung funktionieren soll, wenn KI zuerst findet. Sie befürchten, dass Ruhm an diejenigen geht, die zuerst veröffentlichen oder die stärksten Werkzeuge haben, während das Prüfen und Erklären zu kurz kommt. Ähnliche Sorgen hatten Mathematiker im Juni in der Leidener Erklärung geäußert. Ein Warnsignal ist laut kucoin auch die schiere Menge: Von 722 Mathematik-Manuskripten, die OpenAI Anfang Oktober auf GitHub stellte, enthielten nur 162 ein computergeprüftes Hauptresultat.

Einordnung

Wenn sich die Beweise halten, wäre das eines der bedeutendsten Ergebnisse, die je einer KI zugeschrieben wurden. Dass zwei Labore unabhängig voneinander auf eine Widerlegung kommen, spricht eher für die Behauptung. Praktisch ändert sich für Software und Verschlüsselung vorerst nichts. Für die Forschung ist es trotzdem ein Einschnitt, denn viele Schwierigkeitsbeweise müssen neu begründet werden. Offen bleibt die Frage, an der alles hängt: Prüft Lean wirklich die richtige Aussage? Ein maschinell geprüfter Beweis ist nur so gut wie die Formulierung, die man ihm vorgibt. Genau das untersuchen die Experten jetzt. Hinzu kommt der Kontext: Für OpenAI und Anthropic sind Mathe-Durchbrüche ein Schaufenster für ihre Reasoning-Modelle in einem harten Wettlauf um Investorengeld. OpenAI hat gerade eine Finanzierungsrunde zu einer berichteten Bewertung von 1,25 Billionen Dollar abgeschlossen. Ob aus der Ankündigung ein gesichertes Ergebnis wird, entscheidet sich erst mit dem Urteil der Prüfer.