Am 26. Oktober 2026 reichte OpenAI ein 67-seitiges Manuskript in seinem öffentlichen Repository ein. Auf der Titelseite prangte eine unmissverständliche Botschaft: The Exponential Time Hypothesis is False. In der Autorenzeile stand lediglich ein einziges Wort: „OpenAI“. Begleitet wurde das Manuskript von einem vollständigen, maschinell überprüfbaren formalen Beweisskript in Lean.
Eine Kernannahme, die 27 Jahre lang als Fundament für Hunderte von Arbeiten über Schranken in der theoretischen Informatik diente, wurde durch einen deterministischen Algorithmus zu Fall gebracht. Doch statt einen einseitigen Technologiesieg zu verkünden, wählte OpenAI einen bemerkenswerten Weg: Das Labor lud die ursprünglichen Urheber der Hypothese ein, die Leitung eines unabhängigen Gutachtergremiums zu übernehmen. An den Grenzen der Grundlagenforschung wird der Mensch wieder in seine entscheidende Rolle gerufen – als Instanz des Verstehens und der wissenschaftlichen Urteilskraft.
Deterministischer Algorithmus drückt 3-SAT-Komplexität in den subexponentiellen Bereich
Die Exponentialzeithypothese (ETH) wurde 1999 von Russell Impagliazzo und Ramamohan Paturi formuliert. Sie besagt, dass die Lösung des 3-SAT-Problems im schlechtesten Fall eine Laufzeit von $2^{\Omega(n)}$ erfordert. Über fast drei Jahrzehnte hinweg baute die Forschungsgemeinschaft auf diesem Postulat ein weit verzweigtes System bedingter Schranken auf. Die Annahme, dass für eine Vielzahl NP-vollständiger Probleme keine subexponentiellen Algorithmen existieren, ruhte vollständig auf dieser theoretischen Verteidigungslinie.
Das in OpenAIs Paper dargelegte Theorem 1.1 verändert diese Ausgangslage grundlegend. Das Theorem beweist die Existenz eines deterministischen Algorithmus zur exakten Zählung erfüllender Belegungen für jede $k$-CNF-Formel mit festem $k \ge 2$. Die Laufzeit wird mit $(n+m)^{O_k(1)} \cdot 2^{O_k(\sqrt{n \log \log n / \log n})}$ beziffert. Bei einer Klauseldichte von $m \le Dn$ verengt sich diese obere Schranke weiter auf $2^{O_{k,D}(\sqrt{n/\log n})}$.
Abb.: Die Titelseite des Papers mit der OpenAI-Autorenschaft und dem Abstract, das subexponentielle Laufzeitschranken hervorhebt und die Widerlegung der ETH deklariert. Quelle: GitHub (Repository openai/math)
Die mathematische Zeitschranke liegt streng bei $2^{o(n)}$. Damit wird die von der ETH postulierte strikt exponentielle Mauer rein definitionsgemäß durchbrochen. Entscheidend ist, dass der deterministische Algorithmus nicht nur über die Erfüllbarkeit entscheidet, sondern in polynomiellem Raum die exakte Anzahl der Lösungen ermittelt. Durch die Nutzung algebraischer Strukturen zur Auflösung boolescher Bedingungen umgeht das Verfahren die kombinatorischen Engpässe klassischer Suchalgorithmen.
Die technische Architektur verbindet exakte Zählung, Paritätsprüfungen dünn besetzter Matrizen und Polynominterpolation. Den Kern der Konstruktion bilden sogenannte „Shared Linear Sketches“ und Ersetzungen durch Polynome niedrigen Grades. Dieser Ansatz zieht weitreichende theoretische Konsequenzen nach sich: Max-$k$-SAT lässt sich nun in subexponentieller Zeit bis auf $OPT(F) - \varepsilon m$ approximieren.
Auch die Schrankenhypothesen etlicher graphentheoretischer Probleme geraten ins Wanken. Das Zählen unabhängiger Mengen sowie die Graphfärbung mit fester Farbzahl lassen sich nun in Zeit $2^{o(v)}$ bewältigen; das Zählen perfekter Matchings sinkt deterministisch auf $2^{o(v+e)}$. Eine ganze Kaskade von Schranken, die auf der ETH aufbauten, verliert schlagartig ihre Gültigkeit – die Fachwelt muss die Grenzen feinkörniger Komplexität neu vermessen.
Theoretische Abgrenzung: Warum der Algorithmus P=NP nicht impliziert
Erschütterungen grundlegender Komplexitätshypothesen führen leicht zu Missverständnissen. Unmittelbar nach Erscheinen des Papiers kursierten in Fachforen Spekulationen darüber, ob das Ergebnis $P=NP$ nahelege. Dieser Irrtum entspringt einer falschen Einschätzung der Transitivität subexponentieller Schranken. Angesichts der breiten Aufmerksamkeit lieferten die Autoren auf Seite 2 eine nüchterne theoretische Klarstellung.
Abb.: Seite 2 mit dem Haupttheorem und Laufzeitschranken sowie dem ausdrücklichen Hinweis, dass sich die subexponentielle Schranke nicht über polynomielle Reduktionen auf ganz NP überträgt. Quelle: GitHub (Repository openai/math)
Das Manuskript stellt unmissverständlich klar, dass die Schranke von $2^{o(n)}$ sich nicht über standardmäßige Polynomialzeit-Reduktionen übertragen lässt. Eine Ausweitung auf alle NP-Probleme würde eine weitaus stärkere Schranke der Form $2^{n^{o(1)}}$ voraussetzen. Das Ergebnis steht in keinem direkten Zusammenhang mit der P-gegen-NP-Frage; OpenAI erhebt im Text keinerlei derartige Ansprüche.
Das Forschungsteam stuft das Manuskript als „rohe Forschungsdaten“ (raw research data) ein. Zwar enthält das Lean-Repository ein lückenloses formales Beweisskript, doch die formale Verifizierbarkeit durch Symbole bedeutet keineswegs, dass menschliche Mathematiker die dahinterliegenden Mechanismen unmittelbar begreifen können. Es bedarf der Arbeit von Fachkollegen, um aus dem formalen Code intuitive Modelle zu destillieren.
Formale Verifikationswerkzeuge stellen sicher, dass auf logischer Ebene keine Argumentationslücken existieren. Sie können jedoch nicht begründen, warum eine bestimmte Kombination von Polynominterpolationen erfolgreich ist. Maschinelle Beweise beseitigen logische Schwachstellen, vermögen jedoch kein tiefes Verständnis für die Funktionsweise eines Algorithmus zu generieren. Die kognitive Arbeit menschlicher Mathematiker bleibt an dieser Stelle unersetzlich.
Urheber der Hypothese übernehmen die Prüfung
Im Gegensatz zu typischen Pressekampagnen verzichtete OpenAI auf einseitige Triumphmeldungen. Zusammen mit den Ergebnissen veröffentlichte das Team eine hochkarätig besetzte Liste externer Gutachter, die eingeladen wurden, die Begutachtung des Manuskripts zu leiten. Zu den zentralen Mitgliedern gehören Russell Impagliazzo, Ramamohan Paturi und Ryan Williams.
Diese Auswahl besitzt hohes symbolisches und wissenschaftliches Gewicht. Impagliazzo und Paturi stellten die ETH 1999 gemeinsam mit Francis Zane auf. Ryan Williams wiederum widerlegte vor Jahren mittels Schaltkreisschranken eine stärkere Variante der Exponentialzeithypothese. Indem die Schöpfer der Hypothese gemeinsam mit ihren profiliertesten Erforschern die Rolle der Prüfer einnehmen, tritt ein strenges Peer-Review an die Stelle einseitiger Unternehmensankündigungen.
Um die Unabhängigkeit dieses Netzwerks zu gewährleisten, stellte OpenAI substantielle Mittel bereit: Eine Zuwendung von 5 Millionen US-Dollar floss an die Simons Foundation als Teil einer insgesamt rund 15 Millionen Dollar umfassenden Initiative für theoretische Wissenschaften. Die Gelder finanzieren Fachkonferenzen und Forschungsaufenthalte, damit Wissenschaftler jedes mathematische Lemma im Detail prüfen können.
Diese zurückhaltende Haltung resultiert auch aus Erfahrungen der jüngsten Vergangenheit. Am 6. Oktober hatte OpenAI 722 ungeprüfte KI-Manuskripte auf einen Schlag veröffentlicht, was scharfe Kritik von Spitzenmathematikern wie Terence Tao auslöste. Man warf dem Unternehmen vor, mit einer Flut minderwertiger Texte den wissenschaftlichen Diskurs zu belasten und wertvolle Begutachtungsressourcen zu vergeuden.
Drei Durchbrüche, drei Verifikationsmodelle
In seiner Ankündigung vom 26. Oktober stellte OpenAI zeitgleich drei theoretische Meilensteine vor. Für jede Disziplin wählte das Team einen spezifischen Verifikationspfad, abgestimmt auf deren wissenschaftliche Gepflogenheiten:
In der Informatik stützt sich die ETH-Widerlegung auf eine Kombination aus Open-Source-Transparenz und externer Expertenleitung. Das englische Papier und der Lean-Code wurden parallel veröffentlicht, um eine weltweite Begutachtung zu ermöglichen.
In der harmonischen Analysis wurde der Beweis der lokalen Glättungshypothese (Local Smoothing Conjecture) der freien Rezeption der Fachwelt übergeben. Das Ergebnis entstand am 18. Oktober und wurde am 19. Oktober in Lean verifiziert. Das Manuskript beweist die 1991 von Christopher Sogge aufgestellte Vermutung für die euklidische Wellengleichung in allen Dimensionen und schließt damit langjährige offene Fragen wie die Kakeya- und Stein-Restriktionsvermutungen ein.
Abb.: Titelseite des zeitgleich veröffentlichten Papers zur harmonischen Analysis mit dem Beweis der lokalen Glättungshypothese für alle Dimensionen. Quelle: GitHub (Repository openai/math)
Während in der Analysis kein eigenes Komitee eingesetzt wurde, griff OpenAI in der Hochenergiephysik zu einer strengen Isolationsstrategie. Ein Beweis für die Existenz vierdimensionaler wechselwirkender Quantenfeldtheorien – eine Frage, die direkt das Millennium-Problem zur Yang-Mills-Existenz berührt – wurde vollständig an eine externe Gruppe unter Leitung von Nobelpreisträger David Gross (2004) sowie Michael Douglas und Arthur Jaffe übergeben. Dieses externe Gremium entscheidet eigenständig darüber, wann und in welchem Umfang Daten und Modelldetails publiziert werden.
Dieses dreigleisige Vorgehen basiert auf vier Grundsätzen: vollkommene Transparenz, Verzicht auf Autorenschaftsansprüche für Basismodelle, Anerkennung der akademischen Arbeit externer Wissenschaftler und Unabhängigkeit der Gutachter vor Unternehmensinteressen. Die Anpassung der Verifikationsstrukturen an das jeweilige Fachgebiet stellt ein offenes Experiment zur wissenschaftlichen Governance maschinengenerierten Wissens dar.
Der Wandel der menschlichen Rolle: Vom Beweisen zum Beurteilen
Vom ersten Entwurf des Modells am 16. Oktober bis zum erfolgreichen Durchlauf des Lean-Compilers am 17. Oktober vergingen lediglich wenige Tage. Was die theoretische Informatik über fast drei Jahrzehnte hinweg beschäftigte, durchbrach das System in wenigen Dutzend Rechenstunden. Dieses Tempo sprengt die Zyklen klassischer Fachpublikationen und setzt das traditionelle Peer-Review-System unter beispiellosen Druck.
Dass der Code vom Lean-Compiler akzeptiert wird, bestätigt zunächst nur die formale Widerspruchsfreiheit der Symbolkette. Es entbindet den menschlichen Geist jedoch nicht von der Anstrengung, die mathematische Substanz zu durchdringen. Die wissenschaftliche Gemeinschaft wird Monate benötigen, um die geometrische und kombinatorische Intuition hinter den Formeln freizulegen. Maschinen können lückenlose Beweisketten konstruieren; verstehen können sie diese nicht.
Vor diesem Hintergrund vollzieht sich eine fundamentale Verschiebung wissenschaftlicher Arbeitsteilung. Wenn symbolische Suche und formale Deduktion weitgehend von Algorithmen übernommen werden, wandert der Engpass der Forschung an eine andere Stelle. Der Mensch muss seine Kraft nicht mehr primär im mechanischen Zusammensetzen von Beweisschritten erschöpfen. Die eigentliche Aufgabe der akademischen Gemeinschaft verlagert sich auf die konzeptionelle Abstraktion, die Sinngebung und die finale Urteilsfindung.
Unabhängig davon, ob dieses 67-seitige ETH-Paper der eingehenden Prüfung standhält: Die Strukturen der Wissensproduktion geraten in Bewegung. Dass OpenAI die Begründer der Hypothese an den Gutachtertisch bittet, zeigt, dass algorithmische Berechnungen wissenschaftliche Wahrheit nicht isoliert etablieren können. Maschinen mögen am Ziel formaler Deduktionen zuerst ankommen – doch die Autorität zu entscheiden, ob ein Schritt tragfähig ist, verbleibt in der Hand menschlicher Urteilskraft.
Weiterführende Links:
- OpenAI Research: Manuskript The Exponential Time Hypothesis is False und Lean-Repository
- OpenAI Research: Manuskript Local smoothing for the Euclidean wave equation
- Simons Foundation: Ankündigung der Forschungskooperation zu theoretischer Informatik und Mathematik
