Teorema del incremento lineal de velocidad

El teorema del incremento lineal de velocidad de las máquinas de Turing es un teorema de teoría de la complejidad computacional, que se puede enunciar:

Dado c > 0 y cualquier máquina de Turing que resuelve un problema en tiempo $f(n)\,$, hay otra máquina que resuelve el mismo problema en tiempo $c\cdot f(n)$.

Esbozo de prueba para $c={\frac {1}{2}}$

Suponga que la máquina de Turing M resuelve el problema en $f(n)$ pasos y que tiene $k$ símbolos de cinta y $s$ estados internos. Construya una nueva máquina M' con $k^{3}$ símbolos de cinta donde cada símbolo representa un grupo de 3 símbolos adyacentes en la máquina M.

La cinta de la máquina M' es una representación comprimida de la cinta de la máquina M, donde la célula $i$ en la máquina M' representa la secuencia de células $2i-1$, $2i$ y $2i+1$ de la máquina M (note que estos grupos coinciden parcialmente).

En un paso computacional, M' simula la computación de M hasta que la cabeza de M' salga del grupo de células a la izquierda o la derecha (esta simulación se puede hacer en un solo paso porque M no puede estar en más de $sk^{3}$ estados sin que salga del cacho o repita un estado). Durante esta simulación puede que M acepte, en cual caso M' también acepta, o puede que M rodee, en cual caso M' no hace nada (y así también rodee).

Una sutileza final es que porque los cachos se solapan, cada transición entre cachos en M debe ser transformado en $k$ transiciones entre células en M' para tomar en cuenta la $k$ símbolos diferentes que se podría haber escrito en la célula que pertenece a los dos cachos. La construcción requiere que cada paso computacional en M' corresponde a por lo menos 2 pasos en M. Entonces M' toma no más de $1/2f$($n$) pasos. Por añadir pasos que demoran en M', podemos asegurar que tome exactamente $1/2f(n)$ pasos.

Debe ser fácil ver como generalizar la prueba a todos los valores de $c$, y también que la prueba aplica tanto al espacio como al tiempo.

El teorema del aumento de velocidad linear es la razón que la teoría de complejidad hace caso omiso de factores lineares y representa la complejidad de algoritmos con la cota superior asintótica

Bibliografía

• Christos Papadimitriou (1994): Computational Complexity, Capítulo 2.4 «Linear Speedup». Addison Wesley.

• Datos: Q3527226