KI widerlegt die Exponentialzeithypothese: Was das alles bedeutet

OpenAI und Anthropic haben jeweils einen Beweis veröffentlicht, dass die Exponentialzeithypothese falsch ist.

ETH ist eine 27 Jahre alte Annahme aus der theoretischen Informatik, nach der sich manche Probleme niemals viel schneller als mit Brute-Force lösen lassen. Jetzt sagen die führenden KI-Labore: Das stimmt so nicht.

Halten die Beweise stand, sind sie das bislang bedeutendste KI-generierte Ergebnis in der Informatik. Zudem zwingen sie zur Neubewertung von buchstäblich Hunderten Forschungsarbeiten, die ETH als wahr vorausgesetzt haben.

In diesem Artikel erklären wir, was die Exponentialzeithypothese genau aussagt, und ordnen P vs. NP ein, das damit verwandt ist. Wir schauen uns außerdem an, was die beiden Labore konkret behaupten, wie die Beweise geprüft wurden und was sich für die Kryptografie ändert – und was nicht.

P vs. NP in einfachen Worten

P versus NP fragt, ob jedes Problem, dessen Lösung sich leicht überprüfen lässt, auch leicht zu lösen ist. Es ist eines der sieben Millennium-Probleme – und bleibt auch nach diesen Neuigkeiten ungelöst.

Ein Sudoku veranschaulicht das gut. Eine ausgefüllte Lösung zu prüfen dauert Sekunden: Jede Zeile, Spalte und jedes Kästchen auf Wiederholungen scannen. Die Lösung aus einem weitgehend leeren Gitter zu finden, kann viel länger dauern – und der Abstand explodiert, wenn das Gitter wächst.

• P ist die Klasse von Problemen, die ein Computer in Polynomialzeit lösen kann, also deren Aufwand mit der Eingabegröße n wie n², n³ usw. wächst.
• NP ist die Klasse von Problemen, deren vorgeschlagene Lösungen ein Computer in Polynomialzeit verifizieren kann.

Jedes Problem in P liegt auch in NP. Offen ist, ob auch die Umkehrung gilt. Die meisten Informatiker glauben an P ≠ NP – dass also manche Probleme grundsätzlich schwerer zu lösen sind als zu prüfen. Die moderne Kryptografie baut auf diesem Glauben auf: Verschlüsseln ist einfach, aber Entschlüsseln ohne Schlüssel sollte schwer sein.

Was ist die Exponentialzeithypothese?

ETH ist präziser: Sie behauptet, dass ein konkretes NP-Problem, 3-SAT, unabhängig vom Algorithmus exponentielle Zeit benötigt. Russell Impagliazzo und Ramamohan Paturi von der UC San Diego haben sie in den späten 1990ern vorgeschlagen, Francis Zane trug zur Grundlagenarbeit bei.

Das 3-SAT-Problem

Bei 3-SAT bekommst du eine Formel aus n Wahr/Falsch-Variablen und eine Liste von Klauseln. Jede Klausel verknüpft drei Bedingungen mit ODER, zum Beispiel „x₁ ist wahr ODER x₄ ist falsch ODER x₇ ist wahr“. Die Aufgabe ist, eine Belegung der Variablen zu finden, die alle Klauseln gleichzeitig erfüllt.

Brute-Force probiert alle 2ⁿ Belegungen – jede zusätzliche Variable verdoppelt also die Arbeit. Spätestens bei rund 100 Variablen ist das aussichtslos.

Was ETH sagt

ETH besagt, dass es eine Konstante c > 1 gibt, sodass kein Algorithmus 3-SAT schneller als cⁿ löst. Clevere Verfahren können die Basis unter 2 drücken, aber nie bis in den subexponentiellen Bereich. Formal: Es existiert δ > 0, sodass 3-SAT nicht in Zeit O(2^δn) lösbar ist.

Über Jahrzehnte passte der Fortschritt zu diesem Bild. Forschende senkten die Basis Schritt für Schritt, aber sie blieb deutlich über 1. Weil sich 3-SAT in viele andere Probleme umformulieren lässt, wurde ETH zur Arbeitshypothese: Man nutzte sie, um zu argumentieren, dass Probleme wie Clique, Vertex Cover, Independent Set und andere ebenfalls kaum viel schneller lösbar sind. 

Wie das neue Ergebnis einzuordnen ist

Die neue Schranke schreibt man kurz 2^o(n). Die Kosten pro zusätzlicher Variable nähern sich mit wachsendem n der 1 an – genau das, was ETH für unmöglich hielt.

Was OpenAI und Anthropic verkündet haben

Beide Labore haben im Wesentlichen unabhängig denselben subexponentiellen Bound erreicht und beide ihre Arbeiten mit maschinell geprüften Beweisen im Proof Assistant Lean untermauert.

Anthropic sagt, Claude habe den Kernalgorithmus ohne menschlichen Input gefunden, nachdem etwa 14 Millionen Tokens Output erzeugt wurden. Die Methode nutzt Tensornetzwerke und Rangargumente. Forschende halfen anschließend bei der finalen Ausarbeitung.

Warum haben beide Labore es am selben Tag gefunden?

Keines der Labore hat das Timing erklärt. Anthropics Paper bezeichnet die beiden Ergebnisse als unabhängig und zeitgleich, und die beiden Ausarbeitungen gehen mathematisch unterschiedliche Wege zum im Wesentlichen gleichen Bound. 

Mit etwas Kontext wirkt die Überschneidung weniger überraschend. Beide Labore richten ihre Modelle auf lange Listen offener Probleme, und OpenAI allein veröffentlichte Anfang Oktober Hunderte KI-generierte Mathe-Manuskripte. ETH ist eines der bekanntesten Ziele im Feld, und beide Modelle haben aus derselben veröffentlichten Forschung gelernt. Unabhängige, gleichzeitige Entdeckungen sind außerdem ein altes Muster in der Wissenschaft – man denke an Newton und Leibniz bei der Infinitesimalrechnung oder Darwin und Wallace bei der natürlichen Selektion.

Wie belastbar sind die Beweise?

Lean bestätigt, dass eine formale Aussage logisch aus den Axiomen folgt. Es kann jedoch nicht prüfen, ob die formale Aussage inhaltlich genau dem Paper entspricht. Anthropic weist darauf hin, dass keine Maschine diese Übereinstimmung kontrolliert, und OpenAI sagt, seine Lean-Datei beweise eine leicht schwächere Schranke als die Überschrift.

Nun organisieren dieselben Forschenden, die das Problem aufgestellt haben – Impagliazzo und Paturi – zusammen mit Ryan Williams vom MIT Workshops, um zu bewerten, ob die formalen Aussagen ETH wirklich abbilden. Ihr Schreiben betont, dass eine Teilnahme keine Zustimmung bedeutet. Zum Zeitpunkt des Schreibens dieses Artikels hatte noch niemand öffentlich einen Fehler gefunden. 

Williams hat gesagt, Teile von OpenAIs Beweis wirkten routiniert, während „zwei oder drei fremdartig anmutende Teile“ noch genau geprüft werden müssten. Impagliazzo, einer der ETH-Autoren, bezeichnete das Ergebnis als zutiefst überraschend.

Was sich ändert – und was nicht

Praktisch ändert sich heute fast nichts (zum Glück): Die neuen Algorithmen schlagen Brute-Force nur bei Eingaben, die weit größer sind als alles, was ein Computer je halten könnte.

Keine schnelleren SAT-Solver

Anthropics Paper sagt, die Methode schlägt Brute-Force nur bei astronomisch großen Eingaben. Für typische Formeln mit fünf Klauseln pro Variable liegt der Schnittpunkt bei einer Zahl mit etwa 10.000 Stellen. Im allgemeinsten Fall ist es eine Zahl mit rund 100 Millionen Stellen. 

Die Autorinnen und Autoren sagen außerdem, ihr Ansatz werde bei weniger als etwa 10 Millionen Variablen kaum helfen. Die in Chip-Verifikation, Scheduling und Planung genutzten SAT-Solver werden dadurch nicht schneller.

Kryptografie bleibt intakt

Das Ergebnis berührt P vs. NP nicht. Das behauptet auch niemand. OpenAI sagt, man habe geprüft, ob der Algorithmus reale Kryptosysteme bricht, und sei ziemlich sicher, dass das nicht der Fall ist. 

Die Theorie wird umgeschrieben

Den größten Effekt hat es in der Forschung. Härte-Ergebnisse, die auf ETH oder SETH beruhen, brauchen nun ein neues Fundament, und einige Forschende sagen, dass Jahre ihrer Arbeit überprüft werden müssen. Nicht alles fällt jedoch. Anthropic merkt an, dass das Ergebnis das Orthogonal-Vektoren-Problem nicht widerlegt, das viele fein granulare Komplexitätsresultate stützt. 

Warum das für KI zählt

Die Schlagzeile dreht sich weniger um 3-SAT, sondern darum, wer die Antwort gefunden hat: Zwei KI-Systeme haben unabhängig eine Vermutung gekippt, der menschliche Expertinnen und Experten eine Generation lang vertraut haben.

KI als Forschungspartner

Forschende berichten inzwischen von neuen KI-Ergebnissen im Wochentakt, die laufende Projekte durcheinander bringen. Formale Tools wie Lean werden zentral, weil Menschen damit langen maschinengeschriebenen Beweisen vertrauen können, ohne jede Zeile neu herzuleiten.

Versteckte Abkürzungen und Selbstverbesserung

ETH stand für den Glauben, dass es für manche Suchprobleme keine clevere Abkürzung gibt. Wenn das falsch ist, verbergen sich vielleicht auch bei anderen offensichtlich harten Problemen Abkürzungen.

Ich denke an die Algorithmusentdeckung als ein Feld, in dem solche Abkürzungen für die rekursive Selbstverbesserung viel bedeuten könnten – also die Idee von KI-Systemen, die bessere KI mitentwickeln. KI zu nutzen, um schnellere Algorithmen zu finden, ist ein konkreter Weg dorthin, auch wenn dieses Ergebnis das heute nicht direkt leistet.

Was es für Data Practitioners bedeutet

Für alle, die mit Daten bauen, stechen drei Lektionen heraus:

• Komplexitätstheorie ist mehr als Theorie: Zu wissen, warum ein Problem NP-schwer ist, zeigt dir, wann du über Heuristiken, Approximationen oder Solver statt exakter Suche nachdenken solltest.
• Verifikation ist eine Kompetenz: Wenn KI mehr Code und Analysen erzeugt, ist das Prüfen der Ergebnisse (mit Tests, Beweisen oder reproduzierbaren Pipelines) genauso wichtig wie ihre Erstellung.
• Asymptotik kann täuschen: Ein „schnellerer“ Algorithmus in der Theorie kann bei realen Problemgrößen nutzlos sein. 

Fazit

Wenn die Beweise den Expertinnen- und Expertenprüfungen standhalten, reiht sich die Exponentialzeithypothese in die kurze Liste weithin geglaubter Vermutungen ein, die sich als falsch herausstellten (wie Eulers Summe-von-Potenzen-Vermutung). Aber P vs. NP bleibt offen, und Kryptografie ist vorerst sicher.

Die nächsten Wegmarken sind die Review-Workshops unter Leitung der ursprünglichen ETH-Autoren, unabhängige Re-Implementierungen der Algorithmen und die Frage, ob jemand die Schranke weiter verschärft.

Um die Grundlagen hinter Geschichten wie dieser zu legen, schau dir unsere Kurse zu Datenstrukturen und Algorithmen, Python-Programmierung und Machine Learning an. Sie vermitteln das Big-O-Denken, das Ergebnisse wie dieses lesbar macht.