OpenAI hat Lösungen zu drei epochalen mathematischen Problemen veröffentlicht, die Forscher lange vor große Herausforderungen stellten. Eines davon war eine überraschende Widerlegung der Exponential Time Hypothesis (ETH), einer langlebigen Annahme der Informatik, die eine große Rolle dabei spielt, wie wir verstehen, was schwer zu berechnen ist.
Wie bei früheren Beweis-Veröffentlichungen aus dem Frontier-Labor reagierten die wissenschaftlichen Communities mit einer Mischung aus Begeisterung und Bestürzung. Der Anthropic-Mathematiker Levent Alpöge vorgeschlagen dass OpenAI seine Lösungen auf bereits vorhandenen Arbeiten stützte, und Stunden später erklärte Anthropic anschließend veröffentlicht seine eigene Widerlegung von ETH.
Allerdings entwickelt sich OpenAIs Prozess weiter. Diesmal hat das Labor strukturierte seine Veröffentlichungen unterschiedlich für jede der drei beteiligten Disziplinen: Die Mathematiker ließen die Arbeit auf GitHub hochladen; die Informatiker bildeten eine Arbeitsgruppe, forderten, dass die Beweise öffentlich geteilt werden, und dass OpenAI eine Konferenz zu deren Diskussion finanziert; die Physiker bildeten eine Arbeitsgruppe, die festlegen wird, wie ihr Ergebnis veröffentlicht wird.
Der MIT-Professor Ryan Williams ist der Informatiker, der die Reaktion seines Fachgebiets auf den neuen Befund organisiert. Williams, dessen Arbeit sich mit diesen Fragen der Komplexitätstheorie befasst, hat in der Vergangenheit den Ansatz von OpenAI kritisiert. Aufruf seinen Beweis-Abwurf Anfang Oktober eine „DDOS-Attacke auf Mathematiker“ nannte.
Er erklärte TechCrunch jedoch, dass er sich bereit erklärt habe, mit den Frontier-Labs zusammenzuarbeiten, um Ideen zu unterstützen, die für das Gebiet von entscheidender Bedeutung sind. Das Labor bat ihn, bei der Interpretation der Lösung zu helfen, zusammen mit den Informatikern der UC San Diego, Russell Impagliazzo und Ramamohan Paturi, die die ETH erstmals 1999 veröffentlichten.
Ihr erster Schritt war die Veröffentlichung ein offener Brief mit dem Aufruf an Wissenschaftler, sich mit Rückmeldungen zu diesen Problemen zu beteiligen und eine Diskussion über die Normen rund um KI-Beiträge zu ihrer Arbeit zu führen.
„Manche Teile [des OpenAI-Beweises] sind, könnte man vielleicht sagen, Routine, aber ja, es gibt zwei oder drei fremdartig anmutende Teile, und genau diese Teile, die ich gesehen habe, haben mich denken lassen: wow, das ist etwas, an dem die ganze Gemeinschaft gemeinsam arbeiten muss“, sagte Williams gegenüber TechCrunch.
Bist du bereit für P versus NP?
Die ETH gehört zu einer umfassenderen Klasse von Problemen, die als P versus NP bekannt ist und die Informatik und viele andere Bereiche seit Jahrzehnten bewegt. Reduziert gesagt versuchen Forscher zu verstehen, ob jedes Problem, dessen Lösung sich leicht überprüfen lässt (NP), sich auch leicht lösen lässt (P).
Ein einfaches Beispiel ist das Spiel Sudoku: Sobald eine Lösung für ein Rätsel vorliegt, lässt sie sich schnell überprüfen, aber das Finden der Lösung ist zeitaufwendig. Diese Dynamik gilt für eine Reihe wichtiger Probleme, und die Erkenntnis bildet die Grundlage kryptographischer Systeme: Wenn man den Schlüssel zu einer verschlüsselten Nachricht hat, kann man sie entschlüsseln, aber einen wirksamen Code tatsächlich zu knacken dauert zu lange, um nützlich zu sein.
Allerdings konnten Wissenschaftler bislang nicht beweisen, ob das immer gilt. „P = NP besagt, dass man nicht nur Sudoku-Lösungen überprüfen kann, wenn sie existieren, sondern dass man sie einfach generieren kann“, sagte Williams. „P = NP behauptet, dass dies für jedes einzelne Problem gilt, das man schnell überprüfen kann – wenn man es schnell überprüfen kann, kann man es schnell lösen. Das klingt einfach zu gut, um wahr zu sein.“
Deshalb nehmen die meisten Wissenschaftler an, dass P ≠ NP gilt. Die ETH lieferte dafür einen Beleg. Sie besagt im Wesentlichen, dass selbst der schnellste Computer-Algorithmus exponentiell mehr Zeit benötigt, um eine Lösung zu finden, je mehr Variablen in einer bestimmten Klasse kniffliger Logikrätsel entstehen.
OpenAI und Anthropic behaupten, dass ihre Modelle Algorithmen entwickelt haben, die diese Rätsel in „sub-exponentieller“ Zeit lösen, also schneller als die zuvor für möglich gehaltenen Geschwindigkeiten. Wenn das stimmt, könnten sie die EFT widerlegt haben – in wissenschaftlichen Begriffen refutiert – und vielleicht einen Weg für Algorithmen eröffnet haben, die generell P = NP erfüllen.
„Jeder Informatiker sollte wahrscheinlich der Plausibilität von P = NP etwas mehr Gewicht beimessen, aber das Gewicht kann variieren“, sagte Williams. „Ich glaube schon, dass es viele der Intuitionen, die wir zu haben glaubten über … wie handhabbar [schwierige NP-Probleme] sind, gewissermaßen in Frage stellt. Ich glaube auch, dass dies wahrscheinlich nicht die endgültige Antwort ist. Ich glaube nicht, dass OpenAIs Algorithmus möglicherweise der beste Algorithmus sein kann, den man bekommen kann.“
Die Arbeit, die vor Informatikern liegt
Die Beständigkeit der ETH hat dazu geführt, dass sie in den vergangenen zehn Jahren in vielen wissenschaftlichen Arbeiten aufgenommen wurde, die erneut überprüft werden müssten, falls sich die Behauptung der KI-Labore, sie hätten sie widerlegt, als haltbar erweist, sagte Williams.
„Das ist einer der Gründe, warum ich OpenAI gebeten oder gedrängt habe, eine Konferenz zu diesem Thema zu unterstützen – es wird die Arbeit vieler Forscher beeinflussen, und wir müssen herausfinden, was als Nächstes passiert, abgesehen vom Verständnis der Algorithmen. Wir müssen verstehen, wie sich die Grundlagen im Vergleich zu dem, was wir vorher hatten, ändern sollten“, sagte er.
Vor den wissenschaftlichen Bedenken gibt es Fragen zur Cybersicherheit. Williams sagte, ein verbesserter Algorithmus könne bedeuten, dass kryptografische Systeme, die auf bestimmten Schlüsselgrößen beruhen, als gebrochen betrachtet werden könnten. Eine der ersten Fragen, die er OpenAI-Wissenschaftsleiter Dan Roberts stellte, war daher, „ob sie überprüft hatten, ob sich dadurch Kryptosysteme verändern … ob jetzt etwas unsicher ist? Und offenbar haben sie es überprüft, und sie waren ziemlich zuversichtlich, dass dies keine … Brüche nach sich zieht.“
Dieses neue KI-Paradigma wissenschaftlicher Entdeckung steckt noch in den Kinderschuhen, aber Williams sagt, er sei optimistisch, trotz realer Bedenken, insbesondere was die Ausbildung der nächsten Generation von Wissenschaftlern angeht. Als Informatiker, der Mathematik auf hohem Niveau betreibt, ist ihm die Anpassung vielleicht leichter gefallen als reinen Mathematikern.
Dennoch sagt er, dass die KI „die Menschen zwingt, ein wenig ehrgeiziger bei der Art von Arbeit zu sein, die sie verrichten, und tiefer nachzudenken: Wenn all die Dinge, an denen ich früher gearbeitet habe, nun niedrig hängende Früchte für die KI sind, wie kann ich die Messlatte für die Art wissenschaftlicher Fragen, die ich stellen möchte, höher legen?“