Lance Fortnow schreibt seit mehr als zwanzig Jahren über Komplexitätstheorie, und zu Aufregung neigt er nicht. Sein Beitrag zur neuen Behauptung endete mit einem vorsichtigen Satz: „Ich habe den Beweis nicht selbst überprüft, aber man kann inzwischen sicher davon ausgehen, dass die Exponential-Time-Hypothese erledigt ist" (Computational Complexity).
Die Behauptung kommt von zwei Laboren. OpenAI, das Unternehmen hinter ChatGPT, sagt, sein Modell habe die Exponential Time Hypothesis widerlegt, meist kurz ETH genannt. Wenige Stunden später veröffentlichte Anthropic, der Hersteller von Claude, eine eigene Widerlegung (die beiden Assistenten vergleichen wir hier). Anschließend verknüpften Schlagzeilen die Nachricht mit einem Streit unter Mathematikern und mit Sorgen um die weltweite Verschlüsselung. Wir haben die Veröffentlichungen beider Labore, die Einschätzungen von Fachleuten und die Medienberichte gelesen. Unser Fazit ist klar: Das Ergebnis ist wahrscheinlich echt und für Theoretiker wichtig, aber kein Grund, Ihren Datenschutz zu ändern. Zwei der drei Schlagzeilen betreffen andere Streitigkeiten, die dritte handelt von einem Trend.
Was ist die Exponential Time Hypothesis in einfachen Worten?
Beginnen wir mit einem Rätsel namens 3-SAT. Sie bekommen eine lange Liste von Bedingungen über n Wahr-oder-falsch-Schalter, jede in der Form „A oder nicht B oder C", und müssen eine Schalterstellung finden, die alle erfüllt. Eine vorgeschlagene Stellung zu prüfen geht schnell. Eine zu finden ist das Schwierige, ähnlich wie bei einem Sudoku: Ein fertig ausgefülltes Gitter ist leicht zu kontrollieren, ein leeres nicht.
Die ETH, 1999 von Russell Impagliazzo und Ramamohan Paturi (mit Francis Zane) vorgeschlagen, besagt: Jeder Algorithmus für 3-SAT braucht eine Laufzeit, die wie 2 hoch c mal n wächst, für ein festes c größer null (Fortnow). Stellen Sie sich ein Zahlenschloss vor, bei dem jedes zusätzliche Rädchen den Aufwand mit einem festen Faktor multipliziert, sagen wir 1,3. Die ETH sagt: Dieser Faktor lässt sich verkleinern, aber nie auf 1.
Die Widerlegung besagt, dass der Faktor bei wachsenden Formeln gegen 1 schrumpft. OpenAIs Paper nennt laut Fortnow eine Laufzeit von etwa 2 hoch n mal log log n geteilt durch die Wurzel aus log n. Schnell ist das noch lange nicht. Es wächst nur langsamer als jeder feste Multiplikator. Anthropics eigener Text sagt es deutlich: „Das Ergebnis ist rein asymptotisch und sagt nichts darüber aus, Formeln in der Praxis zu lösen" (Anthropic).
Warum interessierte das die Theoretiker so sehr? Die ETH wurde in Hunderten von Arbeiten als Ersatz für die Aussage „dieses Problem lässt sich nicht wesentlich schneller lösen" verwendet (OpenAI). Ist die Hypothese falsch, müssen diese Härte-Argumente neu geprüft werden, auch wenn Fortnow anmerkt: „Dass ETH und SETH scheitern, heißt nicht, dass ihre Implikationen falsch sind."
Mehr als sonst geprüft, aber weniger als geklärt
Die bisherige Prüfung ist mehr, als die meisten Durchbrüche in der ersten Woche erleben. OpenAI sagt, sein Modell habe den Beweis zehn Tage vor der Ankündigung gefunden, und er sei in Lean formalisiert worden, einem Beweisprüfer, der nur Schritte akzeptiert, die er verifizieren kann (OpenAI). Anthropic sagt, ein internes Claude-Modell habe seine Version gefunden, und die Lean-Dateien seien von KI-Modellen geschrieben worden (Anthropic).
Inzwischen haben sich auch Menschen eingeschaltet. Ryan O'Donnell von der Carnegie Mellon University hat eine neu geschriebene Darstellung des Beweises veröffentlicht, und laut Fortnow hat Shiva Kintali eine weitere gepostet; beide zielen auf Einfachheit statt auf die besten Schranken. Timothy Gowers nannte es „sehr überraschend und folgenreich, dass sie falsch ist" (Business Insider).
Offiziell mit der Prüfung betraut sind Impagliazzo, Paturi und Ryan Williams vom MIT. Er sagte TechCrunch, Teile des Beweises seien Routine, aber „es gibt zwei oder drei fremdartig aussehende Teile". Business Insider berichtet, Williams habe das Ergebnis nicht bestätigt, und die Gruppe betone, ihre Beteiligung sei keine Befürwortung. Noch eine Warnung aus Anthropics eigenem Repository: Lean prüft die Beweise, aber „keine Maschine prüft, ob diese Datei das sagt, was das Paper sagt". Ein Mensch muss also die kurze Statement-Datei lesen. Deshalb hat man sie kurz gehalten.
Unsere Einschätzung: Eine Behauptung von zwei Laboren, maschinengeprüfte Beweise und menschliche Neufassungen binnen Tagen sind ungewöhnlich stark. Es bleibt aber eine Behauptung, bis die Expertengruppe und eine Fachzeitschrift etwas anderes sagen.
Geht es im Streit der Mathematiker um dieses Ergebnis?
Meistens nicht. Der „Krach unter Mathematikern", von dem die BBC schreibt, betrifft ein anderes Problem. Der Bericht behandelt den Streit um die Navier-Stokes-Gleichungen: Tristan Buckmaster von der NYU fragte, ob seine Entwürfe, die im Codex-Tool von OpenAI lagen, in OpenAIs eigene Arbeit eingeflossen sein könnten. OpenAI sagte, niemand dort habe die Arbeit des anderen Teams gesehen, und seine Prompts hätten „das System in keiner Weise beeinflussen können".
Die „Scooped"-Schlagzeile von Scientific American betrifft Yang-Mills, ein Problem aus der Physik. Das Magazin schreibt, OpenAI sei offenbar Ethan Sussman, der mit Anthropics Levent Alpöge arbeitet, bei einem Beweis zuvorgekommen. Alpöge widersprach auf X. Mit der Frage, ob der 3-SAT-Algorithmus funktioniert, hat das alles nichts zu tun.
Der ETH-Streit dreht sich um das Vorgehen. Williams nannte eine frühere OpenAI-Veröffentlichung „einen DDoS-Angriff auf Mathematiker" (X) und erklärte sich dann bereit, bei dieser zu helfen. Scientific American schreibt, OpenAIs Vorgehen bei zwei der drei Ergebnisse habe gegen eine klärende Stellungnahme der eigenen Expertengruppe für KI und Mathematik verstoßen, und die zugehörigen Prompts und Gedankenketten seien weiterhin nicht öffentlich. Bei der ETH hat OpenAI dagegen zugesagt, den Beweis zu veröffentlichen und eine Konferenz zu finanzieren.
Bricht das RSA oder die Verschlüsselung auf meinem Handy?
Nein, und zumindest nicht auf diesem Weg. Wir sagen das so klar, weil die Gründe konkret sind. Erstens löst der Algorithmus k-SAT. Fortnow betont, er „liefert nichts Neues für Subset Sum oder das Problem des Handlungsreisenden", weil die Umwandlung in 3-SAT die Zahl der Variablen zu stark aufbläht. Zweitens beruht RSA darauf, dass sich eine riesige Zahl nur schwer in zwei Primzahlen zerlegen lässt (die Financial Times beschreibt das Verfahren, ohne es zu nennen). Das ist ein anderes Problem als das Erfüllen logischer Formeln, und keine der von uns gelesenen Quellen sagt, dass der neue Algorithmus es erreicht. Drittens ist die Schranke asymptotisch: An einem 2.048-Bit-Schlüssel ändert sich auf keiner existierenden Maschine etwas.
Williams sprach die naheliegende Sorge bei OpenAIs Wissenschaftschef Dan Roberts an. Laut TechCrunch fragte er, ob nun etwas unsicher sei, und gab weiter, OpenAI habe das offenbar geprüft und sei „einigermaßen sicher", dass es keine Brüche nach sich ziehe. Das ist aus zweiter Hand und unveröffentlicht, gewichten Sie es entsprechend. Williams sagte auch, ein verbesserter Algorithmus könne bedeuten, dass manche Schlüssellängen als gebrochen gelten müssen.
Darunter liegt eine echte offene Frage. Williams sagt: „Jeder Informatiker sollte der Plausibilität von P = NP wohl etwas mehr Gewicht geben", doch John D. Cook weist darauf hin, dass „der Status von P = NP weiterhin unbekannt ist" (Business Insider). Williams hält den neuen Algorithmus außerdem nicht für den bestmöglichen. Kommt ein schärferer, ändern sich die Argumente.
Der Artikel der Financial Times handelt von einem Trend, nicht von diesem Beweis
Der FT-Artikel handelt von den wachsenden mathematischen Fähigkeiten der KI und von Verschlüsselung allgemein, und in dem Text, den wir lesen konnten, kommt die ETH nicht vor. Seine Quellen sind besonnen. Der australische Mathematiker Geordie Williamson sagte vor Publikum am Imperial College, KI führe zu „einer völligen Neustrukturierung dessen, was Schwierigkeit bedeutet", und wir sollten mit Erschütterungen rechnen. Daniel Shiu von der University of Manchester nannte es ein „erhebliches Risiko" für „mathematischere Formen der Kryptografie", wenn KI Verschlüsselung knackt, und verwies auf einige „weniger ausgereifte" quantenresistente Algorithmen. Die FT selbst schreibt, KI habe „bislang kein zentrales kryptografisches Verfahren gebrochen".
Scott Aaronson ergänzte einen losen Faden: Kryptografie fehle auffällig in OpenAIs früherer Liste von 376 Arbeiten, und in einem Update zu seinem Beitrag schrieb er, seinen Quellen zufolge hätten KI-Firmen begonnen zu untersuchen, ob ihre Modelle Protokolle brechen können. Namen nannte er keine, und wir können es auch nicht.
Unsere Lesart: Die vernünftige Sorge gilt neueren Verfahren, nicht denen in Ihrem Browser. Die NIST-Standards von 2024 umfassen zwei gitterbasierte Verfahren und einen dritten Signaturstandard, der auf einer anderen Art von Mathematik beruht und als Reserve gedacht ist, falls sich das erste als verwundbar erweist.
Was ein kleines Unternehmen tatsächlich tun sollte
Fast nichts, und nichts Dringendes. Der Entscheidungsbaum unten ordnet die drei Situationen, die wir für wichtig halten.
Eine Gewohnheit lohnt sich unabhängig von dieser Geschichte. Die britische Aufsichtsbehörde sagte der FT, Firmen sollten bei der Vorbereitung auf KI- und Quantenrisiken für die Kryptografie „nicht mit dem Handeln warten", und BT will seine Kryptografie „leichter ändern können, wenn sich Standards, Technologien und Bedrohungen weiterentwickeln". Für einen kleinen Betrieb heißt das: Software aktuell halten und Anbieter fragen, wie sie Algorithmen austauschen würden. Unser Framework, um KI-Tools mit Ihren Daten zu vertrauen enthält die Fragen an Anbieter, und das Security-&-Privacy-Board von ToolRank listet Tools nach Kategorie.
Drei Dinge, die Sie beobachten sollten, bevor jemand „geklärt" sagt
Achten Sie auf drei Dinge. Erstens den Bericht der Expertengruppe um Impagliazzo, Paturi und Williams sowie die Konferenz, die OpenAI zu finanzieren zugesagt hat. Zweitens unabhängige Lektüren der Lean-Statement-Dateien, denn dort könnte sich ein subtiler Fehler verstecken. Drittens das Peer-Review in einer Fachzeitschrift, von dem wir bisher keine Spur gefunden haben. Bis das Erste davon vorliegt, würden wir sagen: „sehr wahrscheinlich widerlegt".