Speedup-Theorem

In der Komplexitätstheorie dienen verschiedene Speedup-Theoreme oder 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).

Lineares Speedup-Theorem

Der bekannteste Vertreter ist das lineare Speedup-Theorem, das auch als lineares Beschleunigen bezeichnet wird. Es besagt, dass sich zu jeder Turingmaschine, die ein Problem in $f(n)$ Zeit berechnet und jedem $\varepsilon >0$, eine neue Turingmaschine konstruieren lässt, die das Problem in $g(n)$ Zeit mit $g(n)=\varepsilon \cdot f(n)+n+2$ berechnet. Jede Turingmaschine, die ein bestimmtes Problem in einer bestimmten Zeit löst, lässt sich um einen beliebigen linearen Faktor beschleunigen. 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 (Bandkompression).

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. Hierbei ist zu beachten, dass sich nicht immer das Ausrechnen eines bestimmten Beispiels um einen linearen Faktor beschleunigen lässt, sondern die zur Addition gehörige Turingmaschine für beliebig große Eingaben.

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.