Théorème d'accélération linéaire

Pour toute machine de Turing ${\displaystyle T}$, calculant une fonction ${\displaystyle g}$ en temps ${\displaystyle f(n)}$ (où ${\displaystyle n}$ est la taille de l'entrée) et toute constante ${\displaystyle 1>c>0}$, il existe une machine de Turing ${\displaystyle T'}$ calculant ${\displaystyle g}$ en temps ${\displaystyle 2+n+cf(n)}$[2].

Pour toute machine de Turing ${\displaystyle T}$, calculant une fonction ${\displaystyle g}$ en espace ${\displaystyle f(n)}$ (où ${\displaystyle n}$ est la taille de l'entrée) et toute constante ${\displaystyle 1>c>0}$, il existe une machine de Turing ${\displaystyle T'}$ calculant ${\displaystyle g}$ en espace ${\displaystyle cf(n)}$.