Back Speedup theorem English Teorema del aumento de velocidad Spanish Teorema dello speedup Italian 加速定理 Japanese Teorema da aceleração Portuguese
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).