Neuer Meilenstein in der Algorithmusforschung: Beweis, dass „ein wenig Speicher mächtiger sein kann als viel Zeit“

• Ein neuer Beweis des MIT-Theoretikers Ryan Williams zeigt, dass Speicherressourcen als Rechenressource mächtiger sein können als Zeit
• Er durchbricht die 50-jährige Stagnation bei der Beziehung zwischen Zeit- und Raumkomplexität und präsentiert eine Methode, alle Algorithmen in Varianten mit geringerem Speicherbedarf zu überführen
• Der Kern des Beweises ist die Verallgemeinerung speichersparender Simulationen, mit der sich der Speicherverbrauch von Algorithmen auf das Niveau der Quadratwurzel der Zeit senken lässt
• Dadurch wurden Fortschritte erzielt, den Unterschied zwischen den Klassen PSPACE und P quantitativ zu belegen, und es eröffnet sich die Möglichkeit, noch größere Lücken nachzuweisen
• Fachleute bewerten das Ergebnis als „erstaunlichen Fortschritt und Ausgangspunkt für neue Entdeckungen“; künftig könnte es ein Hinweis zur Lösung weiterer schwieriger Probleme der theoretischen Informatik sein

---

One Small Step for Space, One Giant Leap for Complexity

Überblick über Ryan Williams’ neuen Beweis

• Im Sommer 2024 bemerkte Ryan Williams vom MIT beim Prüfen seines Beweises, dass eine Idee, die er für einen Fehler gehalten hatte, tatsächlich gültig war
• Er schlug ein allgemeines Verfahren vor, um alle Algorithmen so zu transformieren, dass sie mit weniger Speicher laufen
• Dadurch lässt sich zeigen, dass sich manche Probleme nicht innerhalb begrenzter Zeit lösen lassen

Zeit und Raum: zwei Ressourcen des Rechnens

• Jeder Algorithmus verwendet Zeit und Speicher (Raum)
• Bisher nahm man an, dass bei der Lösung bestimmter Probleme der Raum proportional zur Zeit ist
• Williams’ Beweis etabliert mathematisch, dass Raum mächtiger sein kann als Zeit

Anfänge und Geschichte der theoretischen Informatik

• Juris Hartmanis und Richard Stearns formulierten in den 1960er Jahren die Definitionen von Zeit- und Raumkomplexität
• Damit legten sie die Grundlage, Probleme je nach den zu ihrer Lösung benötigten Ressourcen in Komplexitätsklassen einzuordnen
• P steht für Probleme, die in vernünftiger Zeit lösbar sind, PSPACE für Probleme, die mit angemessenem Speicher lösbar sind

Der erste Fortschritt: die Simulationstechnik von 1975

• Hopcroft, Paul, Valiant entwickelten ein universelles Simulationsverfahren, das jeden Algorithmus in eine Variante mit etwas geringerem Speicherbedarf umwandelt
• Das war ein erster Schritt zum Verständnis des Zusammenhangs zwischen Zeit und Raum, stieß später jedoch an Grenzen
• Wegen der Annahme, dass Daten nicht gleichzeitig denselben Speicherplatz belegen können, galt weiterer Fortschritt als unmöglich

Der Wendepunkt: Squishy Pebbles

• 2010 entwarfen der wegweisende Komplexitätstheoretiker Stephen Cook und seine Kollegen die Aufgabe Tree Evaluation - Pebbles and Branching Programs for Tree Evaluation und bewiesen, dass sie für Algorithmen mit einem Speicherbudget unterhalb einer bestimmten Schwelle unmöglich ist
  • Allerdings gab es eine Schwachstelle. Der Beweis beruhte auf denselben naheliegenden Annahmen, die Paul und seine Kollegen Jahrzehnte zuvor verwendet hatten
  • Nämlich darauf, dass ein Algorithmus keine neuen Daten in einen bereits vollständig belegten Speicher schreiben kann
  • Über mehr als zehn Jahre hinweg versuchten Komplexitätstheoretiker, diese Lücke zu schließen
• James Cook, der Sohn von Stephen Cook, und Ian Mertz veröffentlichten 2023 einen Algorithmus für das Tree-Evaluation-Problem, der mit dieser bisherigen Annahme bricht: Tree Evaluation Is in Space 𝑂 (log 𝑛 · log log 𝑛)
• Sie schlugen ein neues Repräsentationsmodell vor, in dem sich Daten im Speicher physisch überlappen können
• Dieser Ansatz wurde zum Schlüssel, um die bisherigen Grenzen der Simulation zu überwinden

Williams’ entscheidender Sprung

• Angeregt durch einen Vortrag von Studierenden übertrug Williams die Cook-Mertz-Technik gedanklich auf die universelle Simulation
• Die neue Simulation kann den Speicherbedarf eines Algorithmus auf das Niveau der Quadratwurzel seiner Laufzeit senken
• Im Februar 2025 stellte er die endgültige Arbeit auf arXiv, wo sie in der Fachwelt große Anerkennung fand

Was dieses Ergebnis bedeutet

• Der Beweis zeigt nicht direkt, dass PSPACE > P gilt, ist aber ein entscheidender Durchbruch, der in diese Richtung eine Lücke öffnet
• Falls sich das Verfahren künftig wiederholt anwenden lässt, um eine größere Trennung zu erzeugen, könnte man der Lösung des P-vs-PSPACE-Problems näherkommen
• Damit könnte ein Ansatzpunkt zur Lösung eines der ältesten offenen Probleme der Informatik entstanden sein

Ein nachwirkender Schluss

• Williams blickte auf das Ergebnis mit folgenden Worten zurück:
  „Ich habe nicht genau das bewiesen, was ich eigentlich beweisen wollte, aber am Ende war das, was ich bewiesen habe, noch besser als das, was ich mir erhofft hatte.”

[nunojay]

....Äh?

[GN⁺]

Hacker-News-Kommentare

• Wenn man den „fuzz“ weglässt, kann eine Multitape-Turingmaschine, die in Zeit t arbeitet, mit O(sqrt(t log t)) Speicher simuliert werden (meist dauert das dann länger als t an Zeit): Simulating Time With Square-Root Space
  • Schade ist, dass Quanta-Artikel in der Mathematik oft zu viele poetische oder übertriebene Formulierungen mischen und dadurch Missverständnisse erzeugen. Im Quanta-Artikel heißt es: „Bestimmte Aufgaben benötigten Speicher proportional zur Laufzeit“, aber schon aus der Komplexitätshierarchie ergibt sich keine solche allgemeine Intuition. Aus Aussagen über „einige Algorithmen“ kann man keine Gesamtintuition ableiten.
  • Vielleicht will man den Lesern zu sehr entgegenkommen, aber ich fand es etwas herablassend, dass Quanta die Komplexitätsklasse P nur als „alle Probleme, die sich in vernünftiger Zeit lösen lassen“ erklärt und den Begriff polynomial gar nicht verwendet.
• Im „Camel Book“, das die Perl-Philosophie verkörpert, gibt es diese Passage: „Wenn dir der Speicher ausgeht, kannst du welchen kaufen; wenn dir die Zeit ausgeht, gibt es keinen Ausweg.“ Ich mag das Buch einfach, weil es so unterhaltsam ist.
  • Ich denke aber, auch diese Aussage hat zwei Seiten. Ein Programm, das mehr Speicher braucht als der Computer hat, kann man gar nicht erst ausführen; wenn es nur lange dauert, lässt es sich immerhin irgendwie laufen. Insofern ist Zeit ebenfalls eine wichtige Ressource.
• Ein Sieg für Lookup-Tabellen, in denen vorab berechnete Werte gespeichert werden. Früher dachte ich, die Verarbeitungsgeschwindigkeit könnte revolutioniert werden, wenn man alle Berechnungen zentral speichern könnte, sodass man fast keinen Prozessor mehr bräuchte. (Allerdings gibt es da noch das separate schwierige Problem der schnellen Suche.)
  • Als ich früher anfing, an Speichersystemen zu arbeiten, schlug ich vor, einfach alle 4-KB-Blöcke vorab zu berechnen und zu speichern. Dann wies mich jemand darauf hin, dass es mehr eindeutige 4-KB-Blöcke gibt als Atome im Universum, und ich war ziemlich verblüfft.
  • Ein Algorithmus namens HashLife macht in Conways Game of Life etwas Ähnliches auf Turing-vollständige Weise. Ich fand faszinierend, dass man selbst bei sehr komplexen und vielfältigen Zuständen künftige Zustände sprunghaft vorab berechnen kann.
  • Ein Witz dazu: Man könnte ja auch einfach die retrieval-/Lookup-Vorgänge selbst cachen.
  • Auf Community-Ebene wird das faktisch bereits durch die Verteilung vorkompilierter Software umgesetzt. Die traditionelle Hürde, Sprachfeatures aufzugeben, weil sich nicht effizient genug kompilieren lässt, kann durch paralleles Kompilieren in der Cloud und weltweite Caches überwunden werden. Wenn etwas einmal für ein Release kompiliert wurde, können es danach alle gemeinsam nutzen.
  • In Verlängerung der Aussage „Wenn man alle Berechnungen zentral speichert, braucht man wohl keinen Prozessor mehr“ könnte man auch gleich noch die Suchhistorie komplett memoizen.
• Wegen des poetischen Quanta-Stils ist schwer zu verstehen, ob diese Forschung tatsächlich auf praktische Computer anwendbar ist oder nur ein rein theoretisches Szenario beschreibt. Ich frage mich, ob das bedeuten soll, dass ein Computer langsamer wird, wenn er mehr Speicher benutzt.
• Ich programmiere seit Langem Rastergrafik, und der Einsatz von Lookup-Tabellen ist mir dadurch ganz natürlich in Fleisch und Blut übergegangen. In letzter Zeit entwickle ich ein Server-Tool, das verschiedene Formen vorab in eine DB legt und bei jeder Abfrage optimierte Ergebnisse verwendet. Das ist kein kompliziertes, sondern ein intuitives Muster. Ich habe das nicht speziell von einem MIT-Professor gelernt, sondern einfach als praktische Arbeitsweise verinnerlicht. Deshalb freut es mich, einen mathematischen Beleg dafür zu sehen. Viele algorithmische Kniffe stammen letztlich oft aus der Erfahrung von Praktikern. (z. B. der Winding-Number-Algorithmus)
  • Die Fortschritte, die ich beim Optimieren von Spielen derzeit erziele, beruhen alle darauf, Lookup-Tabellen situationsgerecht zu behandeln. Es müssen nicht zwingend statische Arrays sein, um als Lookup-Tabelle zu gelten; auch Daten, die sich im Lauf der Zeit leicht verändern, lassen sich ähnlich nutzen. Ich habe angefangen, mehr Arbeit auf der GPU zu erledigen, und es ist effizient, Tabellen, die früher beim Kompilieren oder zur Laufzeit statisch erzeugt wurden, während der Laufzeit teilweise zu ändern und dann wie Texturen an die GPU zu übergeben. Dadurch verschwimmt die Grenze, was man noch als Lookup-Tabelle bezeichnet.
• Es erscheint mir intuitiv, dass Raum (Speicher) viel mehr Ergebniswerte ausdrücken kann als Zeit. Bei einer Bandlänge n kann man zwar O(n) Zeit lang schreiben, aber bei einem binären Band gibt es für Länge n gleich 2^n mögliche Konfigurationen. Wenn man Speicher richtig nutzt, gewinnt man gegenüber Zeit eine viel größere Ausdruckskraft.
  • Meine Intuition: In einer einzigen Zelle können Zwischenergebnisse aus Hunderten von Rechenschritten gespeichert werden. Wenn man solche Zwischenergebnisse nicht speichern kann und jedes Mal alles neu berechnen muss, sinkt die Effizienz stark. Eine Cache-Trefferquote von 0 % ist sehr selten, meistens kann man durch Speichern effizienter werden. Umgekehrt ist es schwer, mit einer Zeiteinheit den Speicher von Hunderten Zellen zu ersetzen, und in heutigen Rechenarchitekturen ist unendliches SIMD nicht möglich.
  • Die Annahme von O(1)-Zufallszugriff auf Speicher wird viel zu selbstverständlich gemacht, tatsächlich steigen die Zugriffskosten mit der Größe des Computers bis auf O(n^(1/3)). In Rechenzentren kann man das sehr direkt spüren. Ich meine mich zu erinnern, dass das ein anderes Modell als UMA war.
  • Solange P ≠ PSPACE nicht bewiesen ist, ist das ein Bereich, in dem mathematische Beweise schwieriger sind als Intuition.
  • Andererseits stimmt es zwar, aber bei Problemen, die sich schwer parallelisieren lassen (z. B. alternating machine PTIME=PSPACE), bringt mehr Speicher möglicherweise keinen großen Vorteil. Im Paper ist der Sprung von t/log t auf sqrt(t log t) revolutionär, aber es dürfte grundlegende Grenzen geben, die selbst durch unendliche Parallelisierung nicht überwunden werden.
  • In der Praxis hängt es von der Art der Aufgabe ab. Wenn Speicherzugriffe viel langsamer sind als eine Zuweisungsoperation, kann Neuberechnung manchmal schneller sein.
• Die „umgekehrte Beziehung“ zwischen Zeit und Raum lässt sich als Phänomen erklären, dass man, wenn eine Ressource beschränkt ist, nicht automatisch das Optimum bei der anderen bekommt. Bei Sortieralgorithmen mit drei Nebenbedingungen – Zeit, Speicher und Stabilität – verschlechtert sich etwa Zeit- oder Speichereffizienz, wenn zusätzlich Stabilität erfüllt sein muss. Bis heute gibt es kein stabiles Sortierverfahren, das ebenso schnell ist und ebenso wenig Speicher braucht wie die besten instabilen Verfahren.
• Mir persönlich gefällt der Stil der Artikel im Quanta Magazine. Er erweitert den Horizont nicht nur für Informatiker, sondern auch für interessierte Laien aus verwandten Bereichen. Diese Vogelperspektive und die zugängliche Art der Erklärung geben oft neue Blickwinkel und Ideen.
• Jemand teilt Links zu einem Vortrag und einem Paper von Ryan Williams.
• Wenn eine Single-Tape-Turingmaschine als Eingabe die Binärzahl N bekommt und rechts auf das Band N-mal eine 1 schreiben soll, scheint sie in Zeit N auch N Zellen Speicher zu brauchen. Wie kann man das dann mit weniger als N Speicher simulieren? Mich interessiert auch, was das wegen der Turingmaschinen-Struktur – bei der man nicht beliebig auf Positionen des Bands springen kann – mit realen Computern zu tun hat.
  • Multitape-Turingmaschinen sind viel schneller als Single-Tape-Maschinen, und mit „Speicher“ ist hier temporärer Arbeitsraum ohne Ein- und Ausgabe gemeint.
  • Das Paper betrachtet vor allem Entscheidungsprobleme, also Situationen, in denen die Ausgabe nur 1 Bit benötigt. Wenn die Ausgabe N Bit lang ist, entspricht das im Grunde dem Aneinanderhängen von N Entscheidungsproblemen.