Die theoretische Informatik beschäftigt sich seit jeher mit der fundamentalen Frage, wie effiziente Algorithmen gestaltet werden können. Dabei stehen vor allem zwei Ressourcen im Fokus: Zeit und Speicher. Jeder Algorithmus benötigt eine bestimmte Laufzeit, um eine Aufgabe zu erledigen, und damit verbunden ist eine Menge an Speicherplatz, in dem Informationen während der Berechnung abgelegt werden. Seit Jahrzehnten galt die Annahme, dass Speicher nur begrenzt Zeit einsparen kann und dass diese beiden Ressourcen in einem bestimmten Verhältnis zueinander stehen. Doch ein bemerkenswerter neuer Beweis stellt diese Annahme auf den Kopf und öffnet Türen für eine völlig neue Betrachtung der algorithmischen Effizienz.
Der Mathematiker und theoretische Informatiker Ryan Williams von MIT hat 2024 eine fundamentale Entdeckung gemacht, die zeigt, dass ein kleiner Speicherplatz in der Lage ist, eine enorm große Zeitersparnis bei sämtlichen Berechnungen auszugleichen. Seine Erkenntnis besagt, dass Speicher – auch genannt Raum – meistens mächtiger ist als Zeit. Wurde bisher angenommen, dass Algorithmen, welche bestimmte Aufgaben lösen, Speicherplatz in etwa proportional zu ihrer Laufzeit benötigen, ließ sich dies nie rigoros widerlegen oder verbessern. Williams gelang nun erstmals eine universelle mathematische Methode, die jeden Algorithmus so transformiert, dass er mit deutlich weniger Speicherplatz auskommt – ein Resultat, das die Informatik seit über 50 Jahren nicht mehr gesehen hat. Bisher basierten viele Fortschritte in der Komplexitätstheorie auf einer Reihe von Simulationen, die zeigen sollten, welche Probleme innerhalb bestimmter Zeit- oder Speichergrenzen gelöst werden können.
Die zentralen Klassen, mit denen Forscher hier arbeiten, tragen Namen wie P und PSPACE. Die Klasse P umfasst alle Probleme, die in polynomieller Zeit lösbar sind – also innerhalb einer vernünftigen und praktikablen Zeitspanne von Computern. PSPACE hingegen umfasst Probleme, die mit polynomiell begrenztem Speicher lösbar sind. Es gilt als wahrscheinlich, dass PSPACE deutlich mächtiger ist als P, was bedeutet, dass es Probleme gibt, die mit beschränkter Zeit nicht effizient lösbar sind, aber mit begrenztem Speicher. Wissenschaftlich beweisen ließ sich diese Vermutung jedoch nie.
Williams’ Beweis liefert nun die stärkste Verbindung zwischen Zeit und Speicher, die jemals gezogen wurde. Die Grundlage für diese neue Erkenntnis lag in der Arbeit von James Cook und Ian Mertz, die 2023 zeigten, dass Daten nicht unbedingt wie isolierte, nicht überlappende „Kieselsteine“ im Speicher behandelt werden müssen, sondern sich „zusammendrücken“ lassen. Diese sogenannte „Squishy-Pebble“-Technik ermöglichte einen Algorithmen, der mit weitaus weniger Speicher als vorher erwartet auskommt. Williams erkannte sofort das Potenzial dieser Technik für die allgemeine Simulation von Algorithmen und entwickelte daraus eine universelle Methode, um Speicherbedarf drastisch zu senken, auch wenn dies erst einmal auf Kosten der Laufzeit geht. Seine Simulation benötigt in etwa nur die Wurzel der ursprünglichen Laufzeit als Speicherplatz, wobei die Prozessdauer sich verlängert.
Praktisch ist die Methode somit weniger relevant, doch theoretisch ist sie revolutionär. Bis zu diesem Durchbruch war die Vorstellung fest verankert, dass man nicht universell Speicher sparen kann, ohne dass enorme Zeitaufwände anfallen, und dies wurde sogar bewiesen – unter der Annahme, dass verschiedene Speicherbereiche stets separate Daten enthalten müssen. Williams‘ Ansatz löst diese Annahme auf, indem er genau diesen Speicherplatz „überschneiden“ und „zusammendrücken“ kann. Dies erlaubt eine Simulation, die Speicher bedarf viel effizienter nutzt als bisher möglich. Der Weg zu dieser Entdeckung war jedoch kein gerader Pfad.
Williams selbst hatte zunächst Zweifel an seinen Ergebnissen und setzte das Projekt zeitweise aus, weil ihm die Beweismethodik und die mögliche Tragweite zu verrückt erschienen. Erst nach wochenlanger sorgfältiger Prüfung und Rücksprache mit anderen Experten war er überzeugt, einen richtig großen Wurf getan zu haben. Der Respekt der Fachwelt war daraufhin entsprechend riesig. Avi Wigderson vom Institute for Advanced Study bezeichnete den Beweis als „überwältigend“ und „schön“ und gratulierte Williams mit einer E-Mail, deren Betreff schlicht lautete: „You blew my mind“. Der Hintergrund dieses wissenschaftlichen Bereichs geht weit zurück in die 1960er Jahre, als Juris Hartmanis und sein Kollege Richard Stearns die ersten präzisen mathematischen Definitionen von Zeit- und Raumkomplexität entwickelten.
Sie legten das Fundament dafür, wie Algorithmen hinsichtlich der benötigten Ressourcen bewertet werden. Später in den 1970er Jahren arbeiteten John Hopcroft, Wolfgang Paul und Leslie Valiant daran, allgemeine Simulationen zu konstruieren, die versuchten, Zeit- und Speicherverbrauch algorithmisch miteinander in Beziehung zu setzen. Obwohl deren Verfahren erste Fortschritte brachten, blieb der Durchbruch bis heute aus – bis Ryan Williams sein Werk präsentierte. Der revolutionäre Ansatz könnte wichtige Implikationen nicht nur für die reine Theorie, sondern perspektivisch auch für praktische Algorithmen bieten. Indem weniger Speicher benötigt wird, könnten selbst bei komplexen Aufgaben kleine, speicherbeschränkte Geräte effizienter arbeiten können.
Gleichzeitig bleibt es eine Herausforderung, wie sich die verlängerte Laufzeit in der Praxis handhaben lässt. Die Erkenntnisse geben jedoch Hoffnung, dass noch tiefere Einsichten in die Arbeitsweise von Computern bevorstehen und dass weitere langjährige Probleme der Komplexitätstheorie gelöst werden könnten. Williams‘ Beweis hat darüber hinaus gezeigt, dass aus einer positiven Aussage über Speicherverbrauch eine negative Aussage über Zeitverhältnisse folgt: Es existieren Probleme, die nur durch wesentlich höheren Zeitaufwand lösbar sind als durch erhöhten Speicherbedarf. Dies entspricht der Erwartung vieler Forschender, war aber bisher nur schwer mathematisch zu untermauern. Obgleich Williams’ Beweis die Distanz zwischen den Komplexitätsklassen P und PSPACE nicht vollständig überbrückt, so legt er doch – durch bekannte mathematische Analogien – nahe, dass sich die berühmte und offene Frage, ob P ungleich PSPACE ist, mit einer Verfeinerung seines Ansatzes möglicherweise lösen lässt.
Es wird erwartet, dass dafür eine Iteration seines Verfahrens notwendig ist, die den Speicherplatz weiter einschränkt und die Zeitunterschiede noch extremer gestaltet. Allerdings stellt sich die Herausforderung, ob und wie diese mehrfachen Anwendungsschritte möglich sind. Sein Ergebnis ist daher nicht nur ein bedeutender Meilenstein in der Komplexitätstheorie, sondern auch eine Einladung an die globalen Forscherinnen- und Forscher-Communities, die neue Methodik weiterzuentwickeln. Vielleicht steht die Informatik damit vor einem ähnlich grundlegenden Fortschritt wie vor einem halben Jahrhundert. Der Weg zur aktuellen Erkenntnis begann für Ryan Williams bereits in seiner Jugend im ländlichen Alabama.
Dort weckte ein einfacher Computerkurs seine Leidenschaft für Computer und Algorithmen. Später studierte er an der Universität Cornell, wo er sich tief mit der theoretischen Informatik auseinandersetzte und von Wegbereitern wie Juris Hartmanis persönlich betreut wurde. Seine Beharrlichkeit trotz Rückschlagen und die Konzentration auf die Grundfragen der Komplexitätstheorie führten ihn schließlich zu den heute gefeierten Durchbrüchen. Die theoretische Komplexitätstheorie mag auf den ersten Blick abstrakt erscheinen, doch die weitreichenden Folgen reichen bis in die Grundlagen der Informatik. Sie bestimmt, welche Probleme mit Computern überhaupt lösbar sind und wie effizient dies gelingt.
