Fast drei Jahrzehnte lang lag eine Hypothese namens Exponential Time Hypothesis still und leise am Fundament der theoretischen Informatik. Kein Gesetz, kein Theorem, sondern eine so weithin akzeptierte Annahme, dass ganze Forschungsbereiche darauf aufgebaut wurden. OpenAI behauptet nun, dass seine KI-Modelle einen Algorithmus hervorgebracht haben, der sie widerlegt. Wenn sich das Ergebnis hält, reichen die Konsequenzen weit über jedes einzelne Forschungspapier hinaus.
Was die Exponential Time Hypothesis eigentlich besagte
Die Exponential Time Hypothesis, aufgestellt vor rund 30 Jahren, befasst sich mit einer trügerisch einfachen Frage: Wie schnell kann ein Computer bestimmte logische Rätsel lösen? Der unkomplizierteste Ansatz ist Brute-Force, bei dem jede mögliche Kombination aus wahr oder falsch für jede Variable im Rätsel getestet wird. ETH behauptete nicht, dass dies der einzige Weg sei. Sie räumte ein, dass es Abkürzungen gibt. Was sie vorschlug, war eine Untergrenze: Egal wie clever die Abkürzung ist, die erforderliche Rechenarbeit muss mit wachsender Größe des Rätsels dennoch exponentiell steigen.
Das klingt technisch, aber die praktische Auswirkung ist erheblich. ETH war im Wesentlichen ein Tempolimit für eine Klasse von Problemen. Sie sagte Forschern, was im Prinzip machbar war und was nicht. Ganze Zweige von Algorithmen und Komplexitätstheorie wurden mit diesem Limit als gegeben entwickelt.
OpenAI sagt, dass seine Modelle einen Algorithmus entwickelt haben, der dieses vermeintliche Tempolimit knackt. Die Behauptung ist, dass ETH falsch ist.
Der Kaskadeneffekt: Was kaputtgeht, wenn ein Fundament ins Wanken gerät
Das ist es, was die meiste Berichterstattung über die Ankündigung übersieht. Die Geschichte dreht sich nicht nur darum, dass eine Hypothese falsch ist. Es geht darum, was darauf aufgebaut wurde.
Fedor Fomin von der Universität Bergen beschreibt die Reaktion unter Forschern als einen völligen Schock. Er merkt an, dass ein Lehrbuch, das er zu diesem Thema geschrieben hat, obsolet werden würde, falls der Fund bestätigt wird. Das ist keine Hyperbole. Viele Schlussfolgerungen der Informatik wurden unter der Annahme abgeleitet, dass ETH wahr ist. Wenn die Annahme fällt, gelten diese Schlussfolgerungen nicht mehr. Wie Fomin es ausdrückt, würde das Ergebnis eine komplette Überarbeitung mehrerer Bereiche von Algorithmen und Komplexität erfordern.
Leslie Goldberg von der Universität Oxford nennt es unter Vorbehalt einen enormen Durchbruch. Die Bedingung ist wichtig: Der Fund muss noch verifiziert und vor allem verstanden werden. Stefan Szeider von der TU Wien hat überprüft, was OpenAI veröffentlicht hat, und erwartet, dass es einer Überprüfung standhält, merkt jedoch an, dass Forscher immer noch bestätigen müssen, dass die formal bewiesene Aussage das bedeutet, was ihre Autoren sagen, dass sie es bedeutet. Diese Unterscheidung zwischen einem technisch gültigen Beweis und einem Beweis, der das bedeutet, was du denkst, dass er bedeutet, ist keine geringfügige.
ETH ist außerdem mit einem der berühmtesten offenen Probleme der Mathematik verbunden: P versus NP. Dabei geht es um die Frage, ob Probleme, deren Antworten leicht zu überprüfen sind, auch leicht zu lösen sind. Dass ETH wahr ist, hätte impliziert, dass die Antwort nein lautet. Aber Goldberg ist explizit: Die Widerlegung von ETH bedeutet nicht, dass die Antwort ja lautet. Die Frage P versus NP bleibt offen.
OpenAI hat Lean verwendet, ein Software-Tool, das mathematische Beweise formal überprüft, um das ETH-Ergebnis zu verifizieren. Das Unternehmen hat außerdem eine unabhängige Prüfungsgruppe beauftragt, zu der Russell Impagliazzo und Ramamohan Paturi gehören, beide von der University of California, San Diego, die zu den Forschern gehörten, die ETH ursprünglich vorschlugen. Ihr offener Brief beschreibt den Fund als etwas, das einen wichtigen Teil der theoretischen Informatik verändern könnte.
Mathematik per Pressemitteilung, und warum diese Formulierung wichtig ist
Das ETH-Ergebnis war nicht die einzige Ankündigung. OpenAI behauptet auch, dass seine KI eine Vermutung aus dem Jahr 1991 über das Verhalten von Wellen bewiesen hat, mit Auswirkungen darauf, wie sich Wellen ausbreiten und wie dünn eine Form sein kann, während sie immer noch Liniensegmente enthält, die in alle Richtungen zeigen. In der theoretischen Physik wird behauptet, bewiesen zu haben, dass Quantenfeldtheorien, einschließlich der Quantenchromodynamik, die die starke Kraft beschreibt, die Quarks zusammenhält, mathematisch kohärent und nicht nur experimentell nützlich sind. Arbeiten zur Existenz der reinen Yang-Mills-Theorie, Teil eines millionenschweren mathematischen Problems, wurden nicht öffentlich veröffentlicht, während eine Gruppe unter der Leitung des Nobelpreisträgers David Gross sie untersucht.
Die Breite dieser Ankündigungen hat in akademischen Kreisen Unbehagen ausgelöst. Magnus Wahlström von der Royal Holloway, University of London, beschreibt das Phänomen als Mathematik per Pressemitteilung und äußert die Sorge, dass proprietäre KI-Modelle plötzlich die monatelange Arbeit von Forschern über den Haufen werfen können, ohne den üblichen Prozess der Begutachtung durch Fachkollegen und schrittweisen Verifizierung.
Clément Canonne von der Universität Sydney zieht eine scharfe Trennlinie, an der man festhalten sollte: Etwas zu beweisen und zu verstehen, warum es wahr ist, sind nicht dasselbe. Das Netzwerk von Funden, die sich auf ETH stützten, ist zusammengebrochen. Warum es zusammengebrochen ist, bleibt unbekannt.
Kurz gesagt
Eine Hypothese, die die theoretische Informatik 30 Jahre lang geprägt hat, wurde möglicherweise durch ein KI-Modell widerlegt. Wenn dies bestätigt wird, sind die Implikationen strukturell: Schlussfolgerungen, die über Algorithmen und Komplexitätstheorie hinweg auf ETH aufgebaut wurden, müssten neu überdacht werden. Der Fund wird unabhängig überprüft, unter anderem von Forschern, die die Hypothese ursprünglich aufgestellt haben. Was diesen Moment wirklich ungewöhnlich macht, ist nicht nur das Ergebnis selbst, sondern die Lücke, die es offenbart: KI-Systeme können nun Beweise hervorbringen, die Menschen noch nicht vollständig erklären können. Diese Lücke zwischen Beweis und Verständnis ist der Ort, an dem die echte Arbeit beginnt.
Basierend auf Berichten von New Scientist.