Speedup-Theorem
In der Komplexitätstheorie dienen verschiedene Speedup-Theoreme 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.
Andere Speedup-Theoreme sind das Speedup-Theorem von Blum und das quadratische Speedup-Theorem. Kategorie:Theoretische Informatik