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)}$ .

L'idée principale de la preuve est de coder plusieurs lettres en une seule : en faisant des groupes de lettres on peut utiliser moins de place (puisque seul compte le nombre de cases utilisées et pas la taille des lettres) et « sauter » de groupe de lettres en groupe de lettres, ce qui prend moins de temps.En faisant des groupes de 1/c lettres on obtient les résultats annoncés.

L'idée est simplement que plusieurs calculs peuvent être faits en une étape de calcul. Ceci est comparable au changement de taille des registres de processeur de 32 à 64 bits^[3].

En théorie de la complexité, les constantes multiplicatives ne sont pas prises en compte.

• Portail de l'informatique théorique