Eine jahrzehntealte Annahme über die Grenzen der Informatik könnte auf einen unerwarteten Herausforderer gestoßen sein: künstliche Intelligenz.
Am 26. Okt. gab das Unternehmen bekannt, dass seine Modelle einen Beweis erstellt hätten, der die Exponential Time Hypothesis (ETH) infrage stellt – eine lang bestehende Annahme darüber, wie schwierig bestimmte Rechenprobleme zu lösen sind. Forschende haben sich in Hunderten Studien auf die ETH gestützt, und die neuen Erkenntnisse könnten sie dazu veranlassen, einige ihrer Schlussfolgerungen zu überprüfen.
Ein mathematischer Durchbruch führt jedoch nicht automatisch zu schnelleren Computern. Unabhängige Forschende müssen den Beweis noch prüfen, und die Entwicklung praxistauglicher Algorithmen auf Grundlage des Ergebnisses könnte erheblich mehr Arbeit erfordern.
Wie OpenAIs KI eine grundlegende Annahme der Informatik infrage stellte
Laut der Ankündigung von OpenAI erstellten die KI-Modelle des Unternehmens am 16. Okt. einen Beweis, der die ETH infrage stellt. Am folgenden Tag nutzte das Unternehmen Lean, ein Werkzeug zur Überprüfung mathematischer Beweise, um das Ergebnis zu formalisieren.
Die ETH betrifft die Zeit, die zum Lösen bestimmter Rechenprobleme benötigt wird, insbesondere die Boolesche Erfüllbarkeit beziehungsweise SAT. Vereinfacht gesagt besagt sie, dass kein Algorithmus jede Instanz des standardmäßigen 3-SAT-Problems in subexponentieller Zeit lösen kann, wenn die Zahl der Variablen zunimmt.
Die Hypothese hat Forschenden dabei geholfen, bedingte Grenzen dafür festzulegen, wie effizient andere Rechenprobleme gelöst werden können. Sollte die ETH falsch sein, müssten einige dieser Schlussfolgerungen überdacht werden.
OpenAI bezeichnete die ETH als „allgemein für wahr gehalten“. Seit Jahrzehnten stützen sich Forschende auf sie, um die Grenzen der Berechenbarkeit in Bereichen wie Graphentheorie, Computerbiologie und Datenbanken zu untersuchen.
OpenAI hat beide Versionen des Beweises öffentlich zugänglich gemacht. Russell Impagliazzo und Ramamohan Paturi von der UC San Diego sowie Ryan Williams vom MIT werden eine unabhängige Gruppe leiten, die die Ergebnisse überprüft.
Eine Widerlegung könnte die Algorithmusforschung verändern
Sollte sich der Beweis von OpenAI bestätigen, müssen Forschende möglicherweise frühere Studien überprüfen, die sich auf die ETH stützten, um festzustellen, welche Rechenprobleme schwer zu lösen sind.
Die Anfechtung einer Hypothese zur Rechenkomplexität bedeutet jedoch nicht, dass bestehende Software plötzlich schneller läuft oder komplexe Probleme leichter zu lösen sind.
OpenAI räumte ein, dass weitere Arbeit erforderlich ist: „Die Suche nach solchen Algorithmen und die Überführung theoretischer Fortschritte in praktische Verbesserungen werden umfangreiche weitere Forschung erfordern.“
Interesting Engineering berichtete außerdem über zwei weitere von KI erstellte Beweise zur Vermutung der lokalen Glättung und zu Quantenfeldtheorien. Forschende untersuchen diese Ergebnisse in getrennten Prüfverfahren.
Was eWeek herausgefunden hat: Drei Prüfungen, bevor der Beweis die Informatik verändert
OpenAI hat seinen Beweis veröffentlicht und Pläne für eine unabhängige Prüfung dargelegt. Bevor die Erkenntnisse zu Verbesserungen in der praktischen Informatik führen können, müssen Forschende jedoch noch mehrere Fragen beantworten.
Meilenstein der Forschung | Was bisher erreicht wurde | Was noch geschehen muss |
| Formaler Beweis | Versionen in natürlicher Sprache und für Lean sind öffentlich zugänglich | Unabhängige Forschende müssen den Beweis prüfen und interpretieren |
| Wissenschaftliche Auswirkungen | Der Beweis stellt auf der ETH beruhende Annahmen infrage | Forschende müssen bestimmen, welche früheren Erkenntnisse erneut überprüft werden müssen |
| Praxistaugliche Algorithmen | Es wurden keine schnelleren Algorithmen für den Produktiveinsatz nachgewiesen | Forschende müssen Algorithmen entwickeln und testen, die die Rechenleistung verbessern könnten |
Die Bedeutung des von OpenAI gemeldeten Beweises geht über die Lösung eines schwierigen mathematischen Problems hinaus. Die ETH hat jahrzehntelang die Forschung zur Rechenkomplexität geprägt und Wissenschaftlerinnen und Wissenschaftlern dabei geholfen, Grenzen dafür festzulegen, wie effizient bestimmte Probleme gelöst werden können.
Wird die Widerlegung bestätigt, müssen Forschende möglicherweise Erkenntnisse überprüfen, die von der Hypothese abhängen, während Ergebnisse, die durch andere mathematische Argumente gestützt werden, Bestand hätten.
Die größere Frage ist, ob die Entdeckung letztlich zu besseren Algorithmen führen könnte. Eine Widerlegung der ETH würde theoretisch belegen, dass bestimmte Rechenprobleme schneller gelöst werden können, aber sie würde nicht automatisch Algorithmen hervorbringen, die für Anwendungen in der realen Welt geeignet sind.
Die Überführung dieser mathematischen Erkenntnis in messbare Leistungsverbesserungen könnte jahrelange zusätzliche Forschung erfordern.
Das Ergebnis macht außerdem eine Herausforderung der KI-gestützten wissenschaftlichen Entdeckung deutlich. OpenAI erklärt, sein Beweis sei mithilfe von Lean formalisiert worden, das prüft, ob mathematische Argumente vorgegebenen logischen Regeln folgen.
Die formale Verifikation ersetzt jedoch nicht die unabhängige Prüfung der Annahmen, der Interpretation und der weiterreichenden Auswirkungen eines Beweises. Forschende müssen weiterhin klären, was das Ergebnis für die Rechenkomplexität bedeutet und ob es neue, bedeutsame Ansätze für die Entwicklung von Algorithmen eröffnet
Eine frühere Untersuchung von Scientific American zu KI-gestützter Mathematik zeigte, wie schwierig es für Mathematiker sein kann, von KI erstellte Beweise zu interpretieren – selbst wenn formale Prüfungen ihre Korrektheit stützen.
Die Herausforderung besteht nicht einfach darin festzustellen, ob ein Beweis gültig ist, sondern zu verstehen, warum er funktioniert und wie seine Erkenntnisse die künftige Forschung beeinflussen könnten.
Was der Beweis von OpenAI für Entwickler und Unternehmen bedeutet
Unternehmen sollten nicht erwarten, dass ihre Software aufgrund der Ankündigung von OpenAI schneller läuft. Das Unternehmen hat keine Verbesserungen bei der Datenbankleistung, bei Optimierungswerkzeugen oder bei anderer in der Produktion eingesetzter Software demonstriert.
Für Entwickler und Forschungsteams gibt es mehr zu untersuchen. Sie können den veröffentlichten Beweis prüfen, feststellen, ob ihre bisherige Forschung auf der ETH beruht, und die Ergebnisse der unabhängigen Forschungsgruppe verfolgen.
IT-Verantwortliche haben unterdessen kaum Anlass, aufgrund der Ankündigung allein ihre Infrastrukturpläne oder Softwarebudgets zu ändern. Künftige Verbesserungen der Rechenleistung müssten weiterhin entwickelt, getestet und mit bestehenden Lösungen verglichen werden.
Sollten Forschende den Beweis schließlich nutzen, um schnellere Algorithmen zu entwickeln, könnten die Vorteile auf Branchen übergreifen, die auf komplexe Berechnungen und große Datensätze angewiesen sind.
Bis dahin sind Unternehmen besser beraten, die Rechenleistung danach zu beurteilen, was ihre Systeme tatsächlich leisten können, statt danach, was KI-generierte mathematische Entdeckungen möglicherweise ermöglichen könnten.
Außerdem lesenswert: Mehr darüber, wie OpenAI mit Bedenken zur KI-generierten mathematischen Forschung umgeht, erfahren Sie in dem Beitrag darüber, wie die Zusage von 5 Millionen US-Dollar Mathematiker und unabhängige Überprüfungen unterstützen soll.