In der Informatik haben Zeit und Raum eine andere Bedeutung als in unserer analogen Welt. Zeit bezieht sich auf die Anzahl der Schritte eines Algorithmus, also die Menge an Rechenoperationen; Raum dagegen gibt den dafür benötigten Speicherplatz an. Jeder noch so kleine Task, den ein Computer ausführt, benötigt sowohl Zeit als auch Raum. Doch nun entkräftet ein bahnbrechender Beweis des theoretischen Informatikers Ryan Williams vom Massachusetts Institute of Technology eine 48 Jahre alte Annahme über Raum und Zeit: Computer benötigen demnach - zumindest theoretisch - deutlich weniger Speicherplatz als erwartet.

Williams forscht zur Komplexitätstheorie, einem abstrakten Gebiet der theoretischen Informatik, das sich unter anderem mit der grundlegenden Beziehung zwischen Speicherplatz und Laufzeit beschäftigt. Das ist umso schwieriger herauszufinden, da die beiden Größen - Raum und Zeit - beispielsweise je nach Aufgabe oder Algorithmus völlig unterschiedlich ausfallen können. Vereinfacht lässt sich fragen, wie viel, oder besser wie wenig, Speicherplatz benötigt ein beliebiges Problem, das mit einer bestimmten Anzahl an Schritten gelöst wird. Sprich: Welcher Raum ist mindestens erforderlich, wenn der Algorithmus t Rechenoperationen ausführt? 

Bisher glaubte die Fachwelt, dass ein Computerprogramm mit einer Laufzeit von t Schritten mindestens $\frac{t}{\log (t)}$Bits an Speicherplatz braucht. Das entspricht einer nahezu linearen Beziehung zwischen Raum und Zeit. Beim Symposium der Association for Computing Machinery (ACM) in Prag präsentierte Williams im Juni 2025 sein neues Ergebnis: Jedes abzählbare, in t Schritten lösbare Problem benötigt maximal $\sqrt{t\cdot \log (t)}$Bits an Speicherplatz. »Das Ergebnis zeigt, dass wir mit unserer bisherigen Intuition komplett falsch lagen«, sagte Williams gegenüber »Scientific American«. »Ich dachte, da muss etwas nicht stimmen, denn das Ergebnis ist äußerst unerwartet.«

Mit seinem Beweis entkräftet Williams die bisherige Annahme über praktisch lösbare Probleme. Denn aus mathematischer Sicht unterscheidet sich das Ergebnis von Williams gewaltig vom bisher vermuteten Zusammenhang. An Stelle der beinahe linearen Beziehung zwischen Raum und Zeit ist sie nun über die Quadratwurzel gegeben; bei steigender Schrittzahl t kommt der Unterschied immer deutlicher zum Vorschein.

Williams fand den Beweis durch Reduktion. Das ist eine Methode der theoretischen Informatik, die mittels Abstrahieren die Komplexität von einem oder auch mehreren Problemen reduziert. Dabei vereinfacht man die Probleme auf ein identisches Grundproblem. Dessen Lösung ergibt dann unmittelbar die Lösung aller ursprünglichen Probleme. Ein Beispiel dafür: die Terminplanung mit Freunden und das Auswählen eines Films für einen gemeinsamen Filmabend. Beide Zweige lassen sich auf denselben Stamm zurückführen. Gesucht ist eine sich deckende Schnittmenge aller Beteiligten, also entweder ein freier Termin, an dem alle können, oder ein passender Film, den alle schauen möchten. Die Reduktion macht deutlich, dass beide Probleme auf dieselbe Art gelöst werden können.

Der Beweis von Williams baut auf Ergebnissen von James Cook und Ian Mertz auf. Die beiden Informatiker zeigten im Jahr 2024, dass sich so genannte Bäume (abstrakte Objekte in der Informatik, mit denen hierarchische Strukturen dargestellt werden) mit weniger Speicherplatz auswerten lassen als angenommen. Dafür verwarfen Cook und Mertz die bislang geltende Annahme, dass bereits benutzter Speicherplatz nicht weiterverwendet werden kann. Sie entwickelten einen Algorithmus, der belegten Speicher komprimiert und dadurch Raum für neue Informationen schafft. 

»Das Ergebnis zeigt, dass wir mit unserer bisherigen Intuition komplett falsch lagen«Ryan Williams, Informatiker

Williams gelang es, das ausschließliche für Bäume geltende Verfahren von Cook und Mertz auf ein beliebiges lösbares Problem zu reduzieren. Damit lässt sich jeder in t Schritten berechenbare Algorithmus in einen solchen umwandeln, bei dem der Speicherplatz geschickt wiederverwendet wird. Die zur Ausführung benötigten Informationen passen dann in die Quadratwurzel der ursprünglich erforderlichen Bits.

Aber wie so häufig steckt der Teufel im Detail: Das Ergebnis von Williams beschreibt keine allgemeine Beziehung zwischen Zeit und Raum. Es behandelt nur Probleme, die in »abzählbarer« Zeit »praktisch« lösbar sind; damit deckt es nur eine bestimmte Klasse aller möglichen Probleme ab. Dennoch zeigt Williams' Beweis, dass Speicherplatz weitaus mehr Informationen umfassen kann als zuvor angenommen. Die gleiche Anzahl an Rechenoperationen kann mit deutlich weniger Speicher ausgeführt werden.

»Dieser Fortschritt ist unglaublich«, sagte der Informatiker Mahdi Cheraghchi von der University of Michigan zu »Scientific American«. »Vor diesem Ergebnis gab es Probleme, die sich in einer bestimmten Zeit lösen lassen, von denen man aber dachte, dass sie nicht mit so wenig Platz gelöst werden können.«

Ob die Erkenntnisse konkrete Anwendungen finden, ist fraglich: In der Umsetzung ist der speicherfreundlichere Algorithmus langsamer als der bisherige. Dennoch sind die Informatikerinnen und Informatiker dem allgemeinen Verständnis von Raum und Zeit in ihrem Fach einen Schritt näher gekommen. Laut Cheraghchi ist Williams' Ergebnis »ein Schritt in die richtige Richtung, von dem wir nicht wussten, wie er zu gehen war.«