OpenAI erklärte am 26. Oktober 2026, ein internes System habe ein Ergebnis hervorgebracht, das nach Ansicht des Unternehmens die Exponential Time Hypothesis (ETH) widerlegt. Die ETH ist eine Vermutung über den Rechenaufwand für das Erfüllbarkeitsproblem der Booleschen Logik im schlimmsten Fall. Die Lean-Dokumentation beschreibt einen Satz zum exakten Zählen erfüllender Belegungen für bestimmte k-CNF-Formeln. Eine externe Prüfung des ETH-Ergebnisses war damit noch nicht abgeschlossen.
Was OpenAI behauptet
OpenAI datiert das Ergebnis in natürlicher Sprache auf den 16. Oktober und dessen Formalisierung in Lean auf den 17. Oktober 2026. Am 26. Oktober kündigte das Unternehmen außerdem eine externe Gruppe an, die das Ergebnis prüfen und einordnen soll. Zu ihren Leitern gehören Russell Impagliazzo, Ramamohan Paturi und Ryan Williams.
Lean ist ein Beweisassistent, mit dem sich mathematische Aussagen formal ausdrücken und prüfen lassen. Die Formalisierung betrifft einen präzisen mathematischen Satz. Die Deutung dieses Ergebnisses als Widerlegung der ETH ist eine weitergehende Behauptung von OpenAI. ExplainX berichtete am 28. Oktober 2026, dass bis dahin keine unabhängige Bestätigung vorlag.
Was die Lean-Dokumentation formalisiert
Die öffentliche Lean-Scope-Dokumentation beschreibt eine deterministische Maschine, die für kanonisch kodierte k-CNF-Formeln mit festem k ≥ 2 die erfüllenden Belegungen exakt zählt. Dabei bezeichnet L die Bitlänge der Kodierung und n die Zahl der Variablen. Die angegebene Laufzeit lautet:
(L+1)^{O_k(1)} 2^{O_k(n(log log n)^2/√log n)}
Als separate Ressourcenangabe nennt die Dokumentation höchstens (L+1)^{O_k(1)} insgesamt besuchte Bandzellen. Das ist der Umfang des dort beschriebenen Lean-Satzes: exaktes Zählen für diese Eingaben mit den angegebenen Schranken.
Warum die Manuskriptgrenze anders ausfällt
Dieselbe Scope-Seite führt für das Manuskript vom 25. Oktober eine schärfere Laufzeitschranke an: (n+m)^{O_k(1)} 2^{O_k(n log log n/√log n)}, wobei m die Zahl der Klauseln bezeichnet. Sie nennt außerdem eine weitere Schranke für den Fall m ≤ Dn mit festem D > 0: (n+m)^{O_{k,D}(1)} 2^{O_{k,D}(n/√log n)}.
Diese Laufzeitangaben sind dem Manuskript zugeordnet, nicht der auf der Scope-Seite angegebenen Lean-Schranke. Für Leserinnen und Leser ist das ein wichtiger Unterschied: Die beiden Ausdrücke beschreiben nicht dieselbe formalisierte Laufzeit. Die weitergehende Manuskriptgrenze sollte daher nicht mit dem konkreten Laufzeitsatz der Lean-Dokumentation gleichgesetzt werden.
Was die Behauptung für Theorie und Praxis bedeutet
Die ETH steht in engem Zusammenhang mit Fragen zur Komplexität von Algorithmen. OpenAI kündigte damit jedoch keine Lösung des P-NP-Problems an. Auch folgt aus einer asymptotischen Laufzeitschranke nicht unmittelbar, dass gewöhnliche Computer oder SAT-Löser schon schneller arbeiten. OpenAI zufolge ist erhebliche weitere Forschung nötig, um theoretische Fortschritte in praktische Verbesserungen umzusetzen.
Ein englischsprachiges Erklärvideo von Adem B10 führt mit einem vereinfachten Schalterrätsel in ETH und asymptotische Laufzeitgrenzen ein. Das Rätsel ist eine Illustration des Videoautors, nicht OpenAIs Algorithmus.
