Analyse

OpenAI und Anthropic sagen, KI habe die Exponential Time Hypothesis widerlegt, doch der Beweis ist nicht zertifiziert und der Gewinn beginnt erst bei astronomisch großen Eingaben

OpenAI und Anthropic sagen, KI habe die Exponential Time Hypothesis widerlegt. Impagliazzo nennt es schockierend, doch die Prüfung läuft noch.

Von ·

Russell Impagliazzo, der die Exponential Time Hypothesis (ETH) in den 1990er-Jahren mit vorgeschlagen hat, nannte ihre KI-erzeugte Widerlegung eine sehr schockierende Nachricht, so die von AI Weekly am 7. November weitergegebene Presseberichterstattung. Die Einordnung braucht Vorsicht: Zwei Papiere, eines von OpenAI und eines von Anthropic, am 26. Oktober angekündigt, behaupten einen schnelleren Algorithmus für 3-SAT; die Gutachter sagen, ihre Beteiligung sei keine Zertifizierung, das Ergebnis löse P gegen NP nicht, und der Gewinn schlägt Brute Force erst bei Eingabegrößen, die weit jenseits des Speicherbaren liegen. Offenlegung: Anthropic entwickelt Claude, das beim Verfassen von Artikeln dieser Seite hilft, und hat eines der beiden Papiere veröffentlicht.

Das Wesentliche

Was gezeigt ist und was nicht

Ein subexponentieller Algorithmus ist nicht polynomiell, daher sagen beide Labore, das Ergebnis löse P gegen NP nicht, und OpenAI betont, der Gewinn gelte nicht für NP-Probleme im Allgemeinen. Die Lean-Prüfung bestätigt die Logik einer formalen Aussage, doch die Gutachter baten um die Rohdaten und eine Konferenz, die OpenAI zu finanzieren zusagte, laut AI Weekly. Berichtete Daten: Die KI fand das Argument in natürlicher Sprache am 16. Oktober, es wurde am Tag darauf formalisiert, die Papiere erschienen am 26. Oktober.

Chips und Verschlüsselung: was feststeht

Die ETH betrifft den Worst Case, die unmittelbare Wirkung liegt also in der Theorie und bei darauf aufbauenden unteren Schranken. Schnellere Chip-Verifikation oder schwächere Verschlüsselung sind langfristige Spekulation. BeInCrypto und Let's Data Science sagen, heutige Kryptografie und industrielle Solver blieben unberührt, und AI Weekly gibt einen Informatiker wieder, der einen Pressetext irreführend nennt. HackerNoon sagt, die Autoren wendeten die Methode auf dem Papier auch auf elliptische Kurven an; eine Prüfung haben wir nicht gesehen.

Was nicht belegt ist

Übersichtstabelle

Übersichtstabelle
PunktWas Stand 7. November 2026 behauptet wirdQuelle
AnkündigungZwei Papiere am 26. Oktober 2026 angekündigt (OpenAI 67 Seiten, Anthropic 49)AI Weekly
Behauptetes Ergebnis3-SAT in Zeit 2^o(n), in Lean geprüftAI Weekly
Break-even-GrößeEtwa 10^2.389 Variablen (OpenAI), 10^10.000 (Anthropic, fünf Klauseln)AI Weekly
GutachterImpagliazzo, Williams, Paturi; gemeinsame Erklärung: keine ZertifizierungAI Weekly
P gegen NPNicht gelöst, laut beiden LaborenLet's Data Science

FAQ

Hat KI bewiesen, dass P gleich NP ist?

Nein. Der behauptete Algorithmus ist subexponentiell, nicht polynomiell, und beide Labore sagen, P gegen NP sei nicht gelöst.

Ist Verschlüsselung jetzt schwächer?

Praktisch nicht. Die gelesenen Medien sagen, eingesetzte Kryptografie sei unberührt, und der Gewinn zeigt sich nur bei absurd großen Eingaben.

Ist der Beweis bestätigt?

Noch nicht zertifiziert. Die Beweise wurden in Lean geprüft, doch die Gutachter sagen, ihre Beteiligung sei keine Zertifizierung, und die Untersuchung geht weiter.

Methode und Grenzen

Quellen geprüft am 8. November 2026. Wir haben weder die beiden Papiere noch die Lean-Dateien noch die ursprünglichen Zeitungsartikel gelesen; wir stützten uns auf AI Weekly, Let's Data Science, HackerNoon, BeInCrypto und Wikipedia. Offenlegung: Anthropic entwickelt Claude, das beim Verfassen von Artikeln dieser Seite hilft. Dies ist keine Anlage- oder Sicherheitsberatung.

Quellen

Einen Fehler in diesem Artikel entdeckt? Melden Sie ihn · Unsere Korrekturrichtlinie

OrigoTech-Logo

Neu: die App iPhone und iPad

OrigoTech ist jetzt eine App für iPhone und iPad

Lies die Artikel nativ, mit „Neu“-Markierungen für Ungelesenes, lokaler Suche und Offline-Lesen bereits geladener Artikel. Kostenlos, ohne Konto, ab iOS 17; zwischen den Artikeln erscheint Werbung.

Rekha-Symbol: ein in einem Strich gezeichnetes Haus

Vom selben Autor Eigenwerbung

Ein Eulerpfad, mit dem Finger gezeichnet

Rekha, das iPhone-Spiel des Autors von OrigoTech: Verbinden Sie alle Punkte in einem einzigen Strich, ohne dieselbe Verbindung zweimal zu ziehen, in 500 Zeichnungen, die alle lösbar sind.

Der OrigoTech-Newsletter

Ein wöchentlicher, mit Quellen belegter Überblick über die Neuigkeiten zu KI-Werkzeugen.

Weiterlesen