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.
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
- Die Behauptung: Das 67-seitige Papier von OpenAI und das 49-seitige von Anthropic stellen 3-SAT-Algorithmen mit Laufzeit 2^o(n) vor, was die ETH widerlegen würde. Beide sagen, KI sei stark beteiligt gewesen und die Beweise seien in Lean geprüft, laut AI Weekly.
- Was die ETH besagte: 3-SAT lässt sich nicht in subexponentieller Zeit lösen. Das ist stärker als P ungleich NP und dient dazu, viele Algorithmen als nahezu optimal zu zeigen, laut Wikipedia.
- Prüfung bisher: Eine Gruppe aus Impagliazzo, Ryan Williams und Ramamohan Paturi hat die Arbeit untersucht. Ihre gemeinsame Erklärung sagt, ihre Beteiligung sei nicht als Zertifizierung zu verstehen, und Williams sprach von einigen fremdartig wirkenden Teilen, die die Community studieren müsse.
- Praktische Reichweite: Externe Schätzungen sehen den Break-even mit Brute Force bei etwa 10^2.389 Variablen für OpenAIs Schranke und 10^10.000 für Anthropics Fall mit fünf Klauseln. Heutige SAT-Solver und Verschlüsselung sind nicht betroffen.
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
- Zertifizierung der Beweise durch die Prüfgruppe: ausstehend, laut AI Weekly.
- Jede nutzbare Beschleunigung bei echten SAT-Instanzen: nicht gezeigt; die Schwellen sind astronomisch.
- Jeder praktische Angriff auf Verschlüsselung oder Chip-Entwurfswerkzeuge: nicht belegt.
- Ob die Aussagen des Wall Street Journal und der New York Times zu Chips und Verschlüsselung über Spekulation hinausgehen: nicht direkt gelesen.
Übersichtstabelle
| Punkt | Was Stand 7. November 2026 behauptet wird | Quelle |
|---|---|---|
| Ankündigung | Zwei Papiere am 26. Oktober 2026 angekündigt (OpenAI 67 Seiten, Anthropic 49) | AI Weekly |
| Behauptetes Ergebnis | 3-SAT in Zeit 2^o(n), in Lean geprüft | AI Weekly |
| Break-even-Größe | Etwa 10^2.389 Variablen (OpenAI), 10^10.000 (Anthropic, fünf Klauseln) | AI Weekly |
| Gutachter | Impagliazzo, Williams, Paturi; gemeinsame Erklärung: keine Zertifizierung | AI Weekly |
| P gegen NP | Nicht gelöst, laut beiden Laboren | Let'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
- AI Weekly: OpenAI's AI Disproof of 1998 ETH Shocks Co-Author Impagliazzo (geprüft am 2026-11-08)
- Let's Data Science: OpenAI and Anthropic Broke a 1999 Conjecture. Both Found It on October 16. (geprüft am 2026-11-08)
- HackerNoon: OpenAI and Anthropic claim AI has disproved a 27-year-old computer science hypothesis (geprüft am 2026-11-08)
- BeInCrypto: OpenAI Says Its AI Refuted the Exponential Time Hypothesis. Is Bitcoin Safe? (geprüft am 2026-11-08)
- Wikipedia: Exponential time hypothesis (geprüft am 2026-11-08)
Einen Fehler in diesem Artikel entdeckt? Melden Sie ihn · Unsere Korrekturrichtlinie