EINE GELIEHENE VOLLE FESTPLATTE MACHT COMPUTER SCHNELLER

Manche Probleme sind billig in der Zeit, aber gierig nach Speicher, andere umgekehrt. Für einige grundlegende Aufgaben haben Theoretiker harte Grenzen für diesen Kompromiss bewiesen: Mit einem kleinen Arbeitsspeicher kann man nicht schnell sein. Ein neues Paper zeigt, dass eine seltsame Ressource diese Grenzen sprengt: ein Speicher, der bereits voll ist und unversehrt zurückgegeben werden muss.

Die geliehene Festplatte

Das Modell heißt katalytisches Rechnen (catalytic computing) und wurde 2014 von Buhrman, Cleve, Koucký, Loff und Speelman eingeführt. Ein Algorithmus erhält einen winzigen sauberen Speicher, in der Größenordnung von log n Bits bei einer Eingabe der Größe n, plus einen riesigen schmutzigen Speicher, der bereits mit beliebigen Daten gefüllt ist, die er nicht gewählt hat. Er darf beide nach Belieben nutzen, aber wenn er anhält, muss jedes Bit des schmutzigen Speichers genau so sein wie vorher.

Die Autoren verwenden das übliche Bild: Sie leihen sich die enorme Festplatte eines Freundes, voller kostbarer digitaler Erinnerungen, um eine Berechnung durchzuführen. Sie wollen keinen Freund verlieren, also stellen Sie am Ende jedes Bit wieder her.

Ursprünglich sollte das Modell beweisen, dass solcher Speicher nutzlos ist. Intuitiv muss man, um alles wiederherzustellen, die gesamte Information behalten, also gewinnt man nie Platz. Überraschenderweise erwies sich das Gegenteil als wahr: Voller Speicher erlaubt es, Probleme zu lösen, die niemand allein mit sauberem Speicher zu lösen weiß. Doch diese Ergebnisse betrafen den Speicherplatz, und die Algorithmen waren extrem langsam.

Schneller als nachweislich möglich

Adelmo Morrison Orozco, Nathan Sheffield und Ryan Williams (MIT) betrachten nun die Geschwindigkeit. Mit logarithmischem sauberem Speicher und einer polynomiellen Menge geliehenen Speichers geben sie Algorithmen an, die:

• eine Liste sortieren und eine diskrete Fourier-Transformation berechnen, in der Zeit n^(1+o(1)), also fast linear;
• Matrizen multiplizieren in der Zeit n^(ω+o(1)), so schnell wie die beste bekannte Methode mit unbegrenztem Speicher.

Ohne die geliehene Platte ist bewiesen, dass das Produkt aus Zeit und Speicher beim Sortieren und bei der Fourier-Transformation mindestens in der Größenordnung von n² liegen muss, bei der Matrixmultiplikation von n³. Diese katalytischen Algorithmen erreichen also Geschwindigkeiten, die kein gewöhnlicher Algorithmus mit wenig Speicher erreichen kann. Die Autoren sprechen vom ersten bedingungslosen Nachweis, dass katalytische Algorithmen ihre nicht-katalytischen Gegenstücke übertreffen.

Umschalten, ablesen, rückgängig machen

Die entscheidende Zutat ist ein kurzer kombinatorischer Trick. Angenommen, ein Algorithmus kann einen Abschnitt des geliehenen Speichers zwischen einem unbekannten Wert τ und τ + x umschalten, wobei x das Ergebnis ist, das ihn interessiert. In einer großen, ebenfalls geliehenen „Hilfstabelle“ addiert man 1 zu einer sorgfältig gewählten Menge von Einträgen. Der Eintrag an Position τ erhöht sich genau dann um eins, wenn x zu einer gegebenen Menge gehört. Dann führt man jeden Schritt rückwärts aus, und die Platte ist wie vorher, bis auf das Stückchen Antwort, das man wollte.

Schichtet man diesen Trick Lage für Lage, lassen sich flache Schaltkreise schnell auswerten. Die Autoren formulieren dann Sortiernetzwerke, schnelle Fourier-Transformationen und schnelle Matrixmultiplikation als solche Schaltkreise um. In der Arithmetik kosten nur die Schichten extra, die zwei Unbekannte miteinander multiplizieren; rein lineare Schichten sind fast umsonst.

Ein fairer Vergleich

Ein Einwand: Die klassischen Grenzen setzen voraus, dass die Antwort einmal, von links nach rechts, auf ein separates Ausgabeband geschrieben wird, während katalytische Algorithmen ihre Antwort in die geliehene Platte schreiben. Das Paper geht darauf ein. Die Autoren zeigen, dass ihre Algorithmen die Antwort in zwei Durchgängen auf ein Ausgabeband schreiben können und dass zwei Durchgänge gewöhnlichen Algorithmen nicht mehr helfen als einer. Die Grenzen gelten also weiterhin, und die Trennung hält. Sie beweisen außerdem, dass ein Durchgang selbst mit der geliehenen Platte nicht genügt: Das Sortieren stößt dann an dieselbe n²-Schranke.

Eine lange Liste von Nutznießern

Dieselben Werkzeuge liefern schnelle katalytische Algorithmen für die Multiplikation großer ganzer Zahlen und Polynome, das Zählen von Dreiecken und das Finden von Cliquen in Netzwerken, das Erkennen von Pfaden und Zyklen sowie die Textmustersuche mit Platzhaltern. Ihre Laufzeiten entsprechen, bis auf kleine Faktoren, den besten bekannten Algorithmen, die so viel Speicher haben, wie sie wollen. In jedem Fall muss der geliehene Speicher genau so zurückkommen, wie er verliehen wurde.