Die beiden führenden KI-Entwickler OpenAI und Anthropic haben am 26. Oktober unabhängig voneinander erklärt, die seit 1999 bestehende Exponential Time Hypothesis (ETH) widerlegt zu haben.
Nachdem OpenAI den Schritt an jenem Montag öffentlich gemacht hatte, zog Anthropic nur wenige Stunden später mit einer eigenen Arbeit zur Widerlegung der zentralen Informatik-Vermutung nach. Die Ankündigungen lösten in der theoretischen Informatik und der KI-Branche ein breites Echo sowie intensive Fachdebatten aus.
Deterministischer Algorithmus für das 3-SAT-Problem
OpenAI legte ein 67-seitiges Papier vor, das auf der Plattform GitHub zugänglich gemacht wurde. Darin beschreibt das Unternehmen einen deterministischen Algorithmus zur Zählung und Lösung des 3-SAT-Problems, der schneller als bisher theoretisch vorhergesagt operieren soll.
Nach Angaben von OpenAI hatte das hauseigene KI-System das Resultat am 16. Oktober ermittelt und den Beweis am Folgetag mithilfe des interaktiven Theorembeweisers Lean formalisiert. Die 1999 von Russell Impagliazzo und Ramamohan Paturi aufgestellte ETH postuliert, dass kein Algorithmus das 3-SAT-Problem in subexponentieller Zeit lösen kann.
Fachleute stellten fest, dass im Lean-Dokument von OpenAI eine schwächere Schranke von 2^(O(n·(log log n)²/√log n)) formalisiert ist, während das Manuskript 2^(O(n·log log n/√log n)) angibt; beide Werte bewegen sich jedoch im subexponentiellen Bereich. Für den praktischen Einsatz in Unternehmen hat der Durchbruch vorerst keine unmittelbaren Auswirkungen.
Der Algorithmus arbeitet Schätzungen zufolge erst ab etwa 10^10.000 Variablen schneller als reine Brute-Force-Verfahren. OpenAI räumte ein, dass die Übertragung der theoretischen Fortschritte in praktische Softwarelösungen erhebliche zusätzliche Forschung erfordere und Betriebe keine Beschleunigung bestehender Systeme erwarten sollten.
Auswirkungen auf Komplexitätstheorie und Kryptographie
Die ETH stützte bislang mehr als 800 wissenschaftliche Arbeiten als Fundament für untere Schranken. Obwohl die ETH die Aussage impliziert, dass P ungleich NP ist, bedeutet ihre Widerlegung nicht den Beweis für die Identität beider Klassen; das Millennium-Problem P-gegen-NP, auf das ein Preisgeld von 1 Million US-Dollar ausgesetzt ist, bleibt weiterhin ungelöst.
Wer sich mit der rasanten Entwicklung von KI-Systemen befasst, muss auch die rechtlichen Leitplanken in Europa kennen. Dieser kostenlose Download verschafft Ihnen den Überblick über Fristen und Pflichten, den Ihre Rechts- und IT-Abteilung jetzt dringend braucht. EU AI Act in 5 Schritten verstehen
Der Informatiker Ryan Williams vom Massachusetts Institute of Technology untersuchte im Auftrag von OpenAI mögliche Auswirkungen auf moderne Kryptosysteme und stellte fest, dass keine Sicherheitsbrüche zu befürchten seien.
OpenAI kündigte den Schritt im Rahmen von drei Durchbrüchen in Mathematik, Informatik und Physik an, wählte jedoch unterschiedliche Zugangsmodelle. Während das mathematische Dokument direkt veröffentlicht wurde, berief OpenAI für die Informatik-Ergebnisse eine externe Arbeitsgruppe mit Impagliazzo, Paturi und Williams ein, die unvergütet und ohne Geheimhaltungsvereinbarungen agiert.
Die Wissenschaftler betonten in einer gemeinsamen Erklärung, dass ihre Beteiligung keine offizielle Bestätigung oder Zertifizierung darstelle. Williams äußerte, er bezweifle die Optimalität des Algorithmus, bezeichnete Teile des Beweises jedoch als außergewöhnlich.
Kontroversen um Priorität und Veröffentlichungsstrategie
Anthropic veröffentlichte am 26. Oktober ein eigenes 3-SAT-Dokument unter dem Namen des KI-Modells Claude und wies den Fund einem internen Forschungsmodell zu. Der Mathematiker Levent Alpöge von Anthropic warf OpenAI vor, das eigene Ergebnis basiere auf Vorarbeiten. Der KI-Forscher Joshua Fonseca Rivera von Anthropic merkte an, die Leistungsfähigkeit maschineller Intelligenz werde oft unterschätzt.
In der Fachwelt fielen die ersten Einschätzungen gemischt aus. Der Forscher Gary Marcus nannte die Entwicklung bedeutend, sofern sie sich als zutreffend erweise, während der Mathematiker Timothy Gowers Zweifel äußerte und den vorgelegten Beweis für fehlerhaft hielt.
Während die theoretische Forschung neue Horizonte eröffnet, stellt die praktische Anwendung von KI Unternehmen bereits heute vor konkrete Compliance-Fragen. Dieser kostenlose Umsetzungsleitfaden zum EU AI Act klärt über Risikoklassen und alle relevanten Übergangsfristen auf. Leitfaden zur KI-Verordnung kostenlos herunterladen
Fedor Fomin von der Universität Bergen sah im Erfolgsfall eine Revision mehrerer Teilbereiche voraus, während Paul Goldberg von der Universität Oxford betonte, dass kein direkter Einfluss auf P-gegen-NP bestehe.
Zudem geriet die Geheimhaltungspolitik von OpenAI in die Kritik: Bereits am 25. Oktober hatte das Beratergremium AGMAI vor Risiken durch ungleichen Zugang gewarnt. Wissenschaftler wie Andreas Karch, Constantin Kogler und Xiaoyu He bemängelten die selektive Informationsvergabe scharf.
Für Amüsement in der Finanzbranche sorgte am Rande eine Verwechslung: Die Abkürzung ETH wurde in Teilen der Krypto-Szene zunächst mit dem Kürzel der Digitalwährung Ethereum gleichgesetzt.