Teorema de aceleración lineal

El teorema de aceleración lineal o aceleración lineal es un teorema de la teoría de la complejidad , un campo de la informática teórica . De hecho, podemos distinguir dos teoremas, uno relativo a las clases de complejidad en el espacio y el otro a las clases de complejidad en el tiempo . Ambos tienen la consecuencia de agrupar las medidas de complejidad que difieren solo por una constante y, por lo tanto, justifica la notación O grande utilizada en el dominio.

El teorema de la aceleración del tiempo se debe a Juris Hartmanis y Richard Stearns .

Declaraciones

Teorema de la aceleración del tiempo

Para cualquier máquina de Turing que calcula una función en el tiempo (donde está el tamaño de la entrada) y cualquier constante , existe una máquina de Turing que calcula en el tiempo . $T$ $gramo$ $f (n)$ $no$ $1> c> 0$ $T '$ $gramo$ $2 + n + cf (n)$

Teorema de la aceleración espacial

Para cualquier máquina de Turing que calcula una función en el espacio (donde está el tamaño de la entrada) y cualquier constante , hay una máquina de Turing que calcula en el espacio . $T$ $gramo$ $f (n)$ $no$ $1> c> 0$ $T '$ $gramo$ $cf (n)$

Idea de la demostración

La idea principal de la prueba es codificar varias letras en una: al hacer grupos de letras podemos usar menos espacio (ya que solo cuenta el número de casillas utilizadas y no el tamaño de las letras) y grupos de “saltos”. Letras en un grupo de letras, lo que lleva menos tiempo. Haciendo grupos de letras 1 / c se obtienen los resultados anunciados.

La idea es simplemente que se pueden realizar múltiples cálculos en un solo paso de cálculo. Esto es comparable a cambiar el tamaño de los registros del procesador de 32 a 64 bits.

Consecuencias

En la teoría de la complejidad, las constantes multiplicativas no se tienen en cuenta.

Notas y referencias

(en) Sanjeev Arora y Boaz Barak , Computational Complexity: A Modern Approach , Cambridge University Press ,2009( ISBN 0-521-42426-7 )
(en) Christos Papadimitriou , Computational Complexity , Addison-Wesley ,1993( ISBN 978-0-201-53082-7 )capítulo 2.4. Aceleración lineal
Sylvain Perifel , algorítmico complejidad , elipses ,2014, 432 p. ( ISBN 9782729886929 , leer en línea ) , cap. 2.1.1 ("Clases de complejidad temporal"), Un poco en retrospectiva, p. 33.