Beschleunigungssatz

In der Komplexitätstheorie dienen verschiedene Speedup-Theoreme (Beschleunigungssätze) für den Nachweis, dass eine Maschine oder ein Algorithmus um einen gewissen Faktor beschleunigt werden kann, wenn bereits eine andere Maschine oder ein anderer Algorithmus bekannt ist.

Die ursprüngliche Version des Speedup-Theorems stammt von Manuel Blum (1967), ist jedoch heute aufgrund der Verwendung beliebiger Komplexitätsfunktionen nicht mehr von großer Bedeutung. Man setzt heute in der Komplexitätstheorie im allgemeinen echte Komplexitätsfunktionen voraus, die gewisse Eigenschaften erfüllen müssen (siehe auch Anforderungen an Schrankenfunktionen).

Der bekannteste Vertreter ist das lineare Speedup-Theorem, das auch als lineares Beschleunigen bezeichnet wird. Das lineare Speedup-Theorem besagt, dass sich zu jeder Turingmaschine, die ein Problem in O(f(n)) Zeit berechnet, eine neue Turingmaschine konstruieren lässt, die das Problem in O(f'(n)) Zeit mit f' = ε·f + n + 2 (0 < ε) berechnet. Dies bedeutet vereinfachend, dass sich jede Turingmaschine, die ein bestimmtes Problem in einer bestimmten Zeit löst, um einen beliebigen linearen Faktor beschleunigen lässt. Die zusätzliche Addition von (n + 2) ergibt sich aus der Notwendigkeit, das Eingabewort der Ausgangsmaschine vollständig einzulesen.

Die Möglichkeit, Turingmaschinen zu beschleunigen verdankt man der freien Wahl des Arbeitsalphabets der Maschine. Dadurch können mehrere Speicherzellen zusammengefasst werden, indem man sie durch eine Zelle repräsentiert.

Andere Speedup-Theoreme sind das Speedup-Theorem von Blum und das quadratische Speedup-Theorem.

Beispiel aus der Mathematik

Die Addition der Binärzahlen 1001101 und 1010011 benötigt je einen Additionsschritt je Ziffernpaar. Insgesamt also sieben. Schreibt man die Zahlen im Dezimalsystem (77 und 83) so benötigt man nur zwei Additionen - allerdings mit größeren Zahlen.

Das Beispiel erklärt auch, warum Programme auf realen Rechnern nicht auf diese Art und Weise beschleunigt werden können. Anders als eine Turingmaschine können binäre Rechner kein anderes Alphabet außer {0,1} verarbeiten.