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 k3 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 No se pudo entender (<math_output_error>): 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


Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Teorema de equipartición — Figura 1. Movimiento térmico de un péptido tipo hélice α. El movimiento vibratorio es aleatorio y complejo, y la energía de un átomo en particular puede fluctuar ampliamente. Sin embargo, el teorema de equipartición permite que se pueda calcular… …   Wikipedia Español

  • Historia del electromagnetismo — La Historia del electromagnetismo, que es el conocimiento y el uso registrado de las fuerzas electromagnéticas, data de hace más de dos mil años. En la antigüedad ya estaban familiarizados con los efectos de la electricidad atmosférica, en… …   Wikipedia Español

  • Flujo sanguíneo — Saltar a navegación, búsqueda Contenido 1 Definición. 2 Introducción 2.1 Valores normales en el humano 2.2 Índice c …   Wikipedia Español

  • Interpretación de Bohm — La interpretación de Bohm (también llamada teoría de la onda piloto o interpretación causal) es una interpretación de la teoría cuántica postulada por David Bohm en 1952 como una extensión de la onda guía de Louis de Broglie de 1927.… …   Wikipedia Español

  • Elasticidad (mecánica de sólidos) — Una varilla elástica vibrando, es un ejemplo de sistema donde la energía potencial elástica se transforma en energía cinética y viceversa. En física e ingeniería, el término elasticidad designa la propiedad mecánica de ciertos materiales de… …   Wikipedia Español


Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.