OpenAI hat ein Mathematikpapier veröffentlicht, dessen Titel erklärt, die Exponential Time Hypothesis sei falsch. Hält der Beweis, fällt eine der Arbeitsannahmen der modernen theoretischen Informatik: dass die schwersten Logikrätsel einer Standardklasse nicht wesentlich schneller lösbar sind als durch Ausprobieren aller Möglichkeiten. Sehr viele veröffentlichte Härteresultate stützen sich auf diese Hypothese, eine bestätigte Widerlegung würde also ein Umdenken im ganzen Fach erzwingen.
Das Papier, datiert auf den 17. Oktober und überarbeitet am 25. Oktober 2026, liegt in OpenAIs öffentlichem Mathematik-Repository auf GitHub und wird allein OpenAI zugeschrieben, ohne einzelne Autoren. Laut Repository stammen die Manuskripte von einem nicht benannten internen OpenAI-Modell und sind als Rohdaten der Forschung zu verstehen, nicht als fertige Aufsätze. Auf mehr als 60 Seiten liefert das Haupttheorem einen deterministischen Algorithmus, der alle erfüllenden Belegungen einer k-CNF-Formel zählt, also einer Logikformel aus Klauseln mit höchstens k Termen, für jedes feste k ab 2. Die Laufzeit wächst ungefähr wie 2 hoch n geteilt durch die Wurzel aus log n, wobei n die Zahl der Variablen ist, und der Speicherbedarf bleibt polynomiell. Das ist langsamer als polynomielle Zeit, aber schneller als jedes 2 hoch eine Konstante mal n, und genau das schließt die Hypothese aus. Lösungen zu zählen ist schwerer, als zu entscheiden, ob es eine gibt, daher widerlegt das Ergebnis auch die Zählversion der Hypothese und, so das Papier, ihre stärkeren Verwandten.
Die Methode ist algebraisch. Nach unserer Lektüre der Einleitung teilt sie die Variablen in Gruppen, übersetzt die Formel in Polynomgleichungen niedrigen Grades und zählt deren gemeinsame Nullstellen mit Interpolation und schneller Summation, aufbauend auf älteren Split-and-List- und Inklusions-Exklusions-Techniken. Das Papier nennt Folgerungen: subexponentielles exaktes Zählen von Graphfärbungen, unabhängigen Mengen und perfekten Matchings sowie Approximationsverfahren für Max-k-SAT. Es betont, dass sich daraus keine schnellen Algorithmen für jedes NP-Problem ergeben, weil Zeitschranken dieser Form sich nicht über gewöhnliche Reduktionen übertragen.
Der Kontext gebietet Vorsicht. Die bisher besten exakten Zählverfahren für 3-SAT liefen noch in klar exponentieller Zeit, und jahrzehntelange Arbeit, darunter der PPSZ-Algorithmus und seine Verfeinerungen, drückte die Basis des Exponenten nur langsam nach unten. Eine der Folgerungen des Papiers stützt sich zudem auf ein weiteres OpenAI-Preprint, The Unique Games Theorem, vom September, das ebenfalls nicht begutachtet ist.
Nichts davon wurde begutachtet, OpenAIs eigenes Repository warnt, dass Ergebnisse ohne formalen Beweis in Lean Fehler enthalten könnten, und veröffentlichte Reaktionen von Komplexitätstheoretikern haben wir nicht gesehen. Ergebnisse dieser Größenordnung wurden schon angekündigt und wieder zurückgezogen, oft wegen einer Lücke, die erst auffiel, als Fachleute jedes Lemma durchgearbeitet hatten. Angemessen ist vorerst Interesse ohne Glauben: Das Papier ist detailliert genug, damit Fachleute es Schritt für Schritt prüfen können, und ihr Urteil wird die Frage schneller klären als jeder Kommentar.