die Aussage, daß es Probleme gibt, für deren Lösung es bzgl. der Rechenzeit einer Turing-Maschine (und auch anderer Rechnermodelle) keine asymptotisch optimale Lösung gibt.

Unter schwachen Vorraussetzungen gibt es für jede beliebige (schnell) wachsende Funktion τ ein Problem so, daß es für jede Turing-Maschine, die das Problem in Zeit t(n) löst, eine Turing-Maschine gibt, die dasselbe Problem asymptotisch in Zeit τ⁻¹ ○ t(n) löst. Die hierbei betrachteten Probleme sind für den Zweck des Speed-up-Theorems konstruiert, so daß das Speed-up-Theorem eine strukturelle Aussage ohne Anwendungen ist.