Irgendwie war das zu befürchten gewesen. Erst Anfang September hatte ein KI-Modell der Firma OpenAI eine Lösung für eines der sechs noch offenen sogenannten Millennium-Probleme gefunden, berühmte mathematische Fragen, auf deren Lösung jeweils eine Million Dollar ausgesetzt sind. Vier Wochen später publizierte die Firma 722 KI-generierte Abhandlungen mit 377 weiteren Resultaten zu teils sehr hochkarätigen mathematischen Fragen, darunter auch überraschende Fortschritte zu drei weiteren Millennium-Fragen, darunter zu der berühmten Riemannschen Vermutung.

Und jetzt das: Am späten Montagabend, dem 26. Oktober, verkündete OpenAI auf seiner Website, ein KI-Modell habe drei weitere Probleme gelöst: einmal eines ein Thema der reinen Mathematik betreffend, die sogenannte Kakeya-Vermutung, für deren Lösung in einem Spezialfall erst in diesem Sommer eine Fields-Medaille vergeben worden war, die höchste Auszeichnung, die einem Mathematiker zuteilwerden kann. Zweitens wurde eine sehr prominente Frage aus der mathematischen Physik beantwortet, nämlich ob bestimmte Quantenfeldtheorien, darunter die, die das Innere von Atomkernen auf fundamentaler Ebene beschreibt, in einem mathematisch strengen Sinn existieren – sie tun es, und das ist faktisch eine Teillösung des fünften der noch offenen Millennium-Probleme.

Ob P ≠ NP ist, ist selbst noch offen

Schließlich lieferte die KI von OpenAI am Montagabend auch noch die Antwort auf eine Frage der theoretischen Informatik, aus einem Gebiet, das auch Komplexitätstheorie genannt wird, weil es dort darum geht, wie komplex es ist, bestimmte Berechnungen algorithmisch durchzuführen – will sagen: wie schnell der Aufwand mit der Größe des Problems steigt. Eine solche Frage stellt, man ahnt es schon, auch das letzte offene Millennium-Problem, das unter der Zeichenfolge P ≠ NP bekannt ist und das grundsätzlich von einem erheblichen praktischen Interesse ist. Denn je nachdem, wie die Antwort ausfällt, sind alle denkbaren Verschlüsselungsalgorithmen, die heute faktisch das Funktionieren unserer digitalen Zivilisation garantieren, vor der Möglichkeit, geknackt zu werden, sicher – oder, nämlich für den Fall, dass P = NP, sie sind es eben nicht.

Nun ist P ≠ NP selbst nicht Gegenstand des aktuellen KI-Resultats, sondern die sogenannte Exponential Time Hypothesis, kurz ETH, was manche wie englisch „Eeth“ aussprechen. Wäre diese Hypothese korrekt, würde daraus automatisch P ≠ NP, woraus die Sicherheit der Menschheit wenigstens in dieser Hinsicht folgen würde. Und wie die allermeisten Informationstheoretiker vermuten (und inständig hoffen), dass dem so sei, so waren sie sich bisher bei der ETH ziemlich sicher, dass sie zutrifft. Geschätzt sind bisher rund achthundert Veröffentlichungen mit mathematischen Aussagen erschienen, die darauf beruhen, dass ETH korrekt ist.

Zwei KI-Modelle kommen am selben Tag zum selben Ergebnis

Aber sie ist falsch. Das demonstriert der von OpenAI veröffentlichte 64-seitige Beweis, der auch in formalisierter Form von einem Computerprogramm auf Korrektheit überprüft wurde, der aber nun erst einmal von menschlichen Mathematikern nachvollzogen werden muss – wie auch alles andere, womit das KI-Unternehmen in diesem Sommer die Welt der Mathematik erschütterte. Immerhin musste OpenAI drei seiner 722 Veröffentlichungen von Anfang Oktober wieder zurückziehen, wegen eines Vorzeichenfehlers, der dem KI-Modell trotz allem unterlaufen war.

Doch im Fall der ETH ist die Hoffnung, es könne ein Fehler vorliegen und die Hypothese doch zutreffen, wohl vergeblich. Denn nur sechs Stunden nachdem die Mitarbeiter der Firma OpenAI ihre Resultate auf dem Online-Repositorium Github veröffentlicht hatten – in den USA war es immer noch Montag, der 26. Oktober –, erschien auf demselben Server auch ein neuer Post aus dem konkurrierenden Unternehmen Anthropic. Deren KI-Modell Claude war, offenbar auf einem etwas anderen Weg, zu dem faktisch selben Resultat gekommen. Das Kuriose: Beide Unternehmen geben an, ihre KI habe das Ergebnis am selben Tag erzielt, dem 16. Oktober 2026.

Brad Pitt will nicht neben Angelina Jolie sitzen

Was besagt nun die Exponential Time Hypothesis? Dazu stelle man sich ein Galadinner vor, an dem, sagen wir, hundert Promis teilnehmen, die sich aber nicht alle leiden können. Um eine Sitzordnung zu finden, welche einen friedlichen Verlauf des Abends ermöglicht, bittet der Veranstalter vorab jeden Gast um drei Bedingungen die Sitzordnung betreffend, die er jeweils eingehalten wissen möchte. Brad Pitt etwa würde dann vielleicht angeben, nichts gegen Anne Hathaway oder Anya Taylor-Joy als Tischnachbarinnen zu haben, aber durchaus etwas gegen Angelina Jolie. Die Aufgabe, gleich mehrere Präferenzen zu erfüllen, die aus jeweils drei durch ein logisches „oder“ verknüpften Bedingungen bestehen, nennt man das 3-satisfiability-Problem, kurz 3-SAT, und das vorgestellte Sitzordnungsproblem ist mindestens so schwierig zu erfüllen wie 3-SAT.

Nun muss man, um eine gegebene Sitzordnung daraufhin zu überprüfen, ob sie die Wünsche aller Gäste erfüllt, lediglich eine Liste abhaken. Der Aufwand A dafür steigt proportional mit der Anzahl n der teilnehmenden Promis. A(n) = n ist dabei ein spezieller Fall von etwas, was Mathematiker ein Polynom nennen. Probleme, deren Lösungen sich derart effizient überprüfen lassen, dass A(n) ein Polynom ist, heißen aus historischen Gründen „nichtdeterministisch polynomial“ oder „NP“. Aber eine geeignete Sitzordnung zur erstellen – oder zu beweisen, dass es keine gibt, die alle Wünsche erfüllt –, ist eine ganz andere Sache.

Die Urheber der Hypothese sollen jetzt die Widerlegung überprüfen

Nach allem, was man bisher weiß, steigt der Aufwand dazu exponentiell mit der Zahl der Gala-Gäste n. Exponentiell bedeutet: Dieses n steht nun im Exponenten, etwa A(n) = 2ⁿ, und dieser Umstand bringt auch die leistungsfähigsten Computer sehr schnell an ihre Grenzen. Das hier zur Illustration angeführte Sitzordnungsproblem, das Nebenbedingungen erfüllen muss, die einem reinen 3-SAT-Problem fehlen, wächst in der simpelsten Lösung sogar überexponentiell: Um hundert Gäste zu platzieren, gibt es weitaus mehr Möglichkeiten als Atome im sichtbaren Universum.

Für reinrassige 3-SAT-Probleme betrug der Aufwand mit steigendem Problemumfang n bis zum Montag etwa A(n) = 1,3ⁿ. Damit waren diese Probleme leichter als die Ausarbeitung der Sitzordnung für die Promi-Gala, aber immer noch exponentiell schwierig. Denn genau das besagt die Exponential Time Hypothesis: Es gibt keinen Algorithmus, der 3-SAT in einer Zeit löst, die nur subexponentiell mit dem Umfang n des Problems wächst. Aufgestellt wurde sie 1999 von Russell Impagliazzo und Ramamohan Paturi, zwei Mathematikern der University of California in San Diego, die zusammen mit Ryan Williams vom MIT nun von OpenAI gebeten wurden, den KI-Beweis des Hauses unabhängig und ohne Vertraulichkeitsvereinbarung – sowie ohne Bezahlung – zu überprüfen.

Ringen um einen Modus Vivendi

Mit der Einbindung der drei Experten sowie der Ankündigung, eine Fachkonferenz zu dem Thema zu finanzieren, reagiert das Unternehmen offenbar auf die Kritik, die ihm nach den Veröffentlichungen der Beweise Anfang September und Anfang Oktober aus Teilen der Mathematik-Community entgegengeschlagen ist. Allerdings muss sich nun erst noch zeigen, ob damit ein Modus Vivendi gefunden wurde für die Mathematik im Zeitalter der Durchbrüche, die in KI-Konzernen erzielt wurden.  „Unser Involvement sollte nicht als Zertifizierung der Behauptung verstanden werden“, warnen Impagliazzo, Paturi und Williams auf einer Website, die sie eigens zur Diskussion des ETH-Themas aufgesetzt haben.

Insbesondere bleibt die Frage ungelöst, wer in diesem und in den anderen Fällen seit dem Sommer 2026 denn den akademischen Ruhm einheimsen darf. Die KI-Unternehmen wollen ihn erklärtermaßen nicht, aber kann man für das bloße Nachvollziehen maschinengenerierter Beweise Fields-Medaillen oder Millenniums-Millionen vergeben? Tatsache ist, dass sich die in den jeweiligen Gebieten forschenden Mathematiker so oder so auf die neuen KI-Beweise stürzen, um sie zu verstehen.

NP und NP-vollständig

Der Widerlegung der Exponential Time Hypothesis dürfte dabei besondere Aufmerksamkeit zuteilwerden, obgleich es sich gar nicht um eine ausgewachsene mathematische Vermutung handelt, wie etwa die von Riemann eine ist, sondern eher um so etwas wie eine Wette. Impagliazzo und Paturi hatten damit die Konsequenz aus vergeblichen Versuchen ihrer Zunft gezogen, für 3-SAT einen Algorithmus mit nur subexponentiell wachsendem Aufwand zu finden. „Wir nennen das eine Hypothese statt eine Vermutung“, erklärte Impagliazzo 2016 in einem Vortrag, „denn ob sie wahr ist oder nicht, ist etwa so wahrscheinlich wie das Ergebnis eines Münzwurfs.“

Warum aber dann das ganze Theater und achthundert mathematische Veröffentlichungen, die auf dieser Hypothese aufbauen? Weil sie Probleme vom Typ 3-SAT betreffen und diese sind nicht nur NP, also mit nur polynomial wachsendem Aufwand zu überprüfen, sondern auch NP-vollständig. So nennt man Probleme, die NP und zugleich „NP-schwer“ sind, was bedeutet, auf ein solches kann jedes andere Problem in NP mit polynomialem Aufwand zurückgeführt werden.

Die Folgen von P = NP

Die eingangs erwähnte größte Frage der theoretischen Informatik ist nun die nach Problemen, die nicht nur mit polynomialem Aufwand zu checken, sondern auch in dieser Weise zu lösen sind und daher in die Komplexitätsklasse „P“ fallen. Ein Beweis, dass auch nur ein einziges NP-vollständiges Problem (also etwa eines vom Typ 3-SAT) in Wahrheit auch in P liegt, würde damit sofort P=NP beweisen – und das bedeutete: Alle leicht, weil mit nur polynomialem Aufwand zu überprüfenden Aufgaben wären irgendwie auch leicht zu lösen, inklusive derer, auf welchen die Sicherheit digitaler Verschlüsselungen oder Kryptowährungen beruht.

Auch wenn ein Beweis von P=NP als solcher noch keinen Algorithmus liefern würde, der eine solche Effizienz an den Tag legt – allein die theoretische Möglichkeit, dass es ihn gibt, wäre ein totales Desaster für die digitale Verschlüsselung, insbesondere in Zeiten, in denen am Codeknacken interessierte Kreise KI-Agenten in Marsch setzen können, um den fraglichen Algorithmus zu finden. Zwar wären dann auch viele wissenschaftliche Fragen mit für die Menschheit vielleicht segensreichen Antworten im Prinzip leichter zu lösen als bisher gedacht, aber sehr viel lieber wäre den Computerwissenschaftlern doch, es gälte P ≠ NP.

Diese Hoffnung ist mit der Widerlegung der Exponential Time Hypothesis noch nicht perdu. „P ist wahrscheinlich immer noch nicht NP“, schrieb etwa Greg Brockman, Präsident und Mitgründer von OpenAI, auf der Plattform X.  Denn die neuen Veröffentlichungen beider KI-Unternehmen zeigen für das NP-vollständige Problem 3-SAT zwar ein subexponentielles Wachstum des Aufwandes, aber kein polynomiales. Damit liegt 3-SAT noch nicht in P.

Und trotzdem ist das Ergebnis eine Bombe. „Ich war sehr überrascht“, sagt Alexander Razborov von der University of Chicago, einer der führenden Experten für die Frage, ob P = NP oder P ≠ NP, der unter anderem zeigen konnte, dass eine wichtige Klasse bekannter Beweismethoden zu schwach ist, um das Problem zu lösen. Razborov zeigt sich auch nicht dadurch beruhigt oder weniger fasziniert, dass die KI-Algorithmen Formeln für A(n) angeben, die nur ein klein wenig effizienter als exponentiell in n sind. „Ein Gegenbeispiel zur ETH bedeutete einen Algorithmus für NP-vollständige Probleme, der in bestimmten Hinsichten besser ist als die bisherigen“, sagt er. „Ein solcher neuer Algorithmus enthält mit großer Wahrscheinlichkeit neue Ideen, sonst hätte man ihn schon längst gefunden.“