En la teoría de la complejidad computacional , el teorema de Savitch , probado por Walter Savitch en 1970, da una relación entre la complejidad espacial determinista y no determinista . Afirma que para cualquier función,
En otras palabras, si una máquina de Turing no determinista puede resolver un problema utilizando el espacio f ( n ), una máquina de Turing determinista ordinaria puede resolver el mismo problema en el cuadrado de ese espacio limitado. [1] Aunque parece que el no determinismo puede producir ganancias exponenciales en el tiempo, este teorema muestra que tiene un efecto marcadamente más limitado en los requisitos de espacio. [2]
Prueba
Hay una prueba del teorema que es constructiva: demuestra un algoritmo para STCON , el problema de determinar si hay una ruta entre dos vértices en un grafo dirigido , que se ejecuta enespacio para n vértices. La idea básica del algoritmo es resolver de forma recursiva un problema algo más general, probando la existencia de una ruta desde un vértice sa otro vértice t que utiliza como máximo k aristas, donde k es un parámetro que se da como entrada al recursivo algoritmo; STCON puede resolverse a partir de este problema estableciendo k en n . Para la prueba de un k camino -Edge de s a t , se puede probar si cada vértice u puede ser el punto medio de la ruta de acceso, mediante la búsqueda de forma recursiva para caminos de la mitad de la longitud de s a u y u a t . Usando pseudocódigo (con una sintaxis muy parecida a Python ) podemos expresar este algoritmo de la siguiente manera:
def k_edge_path ( s , t , k ) -> bool : "" "Teorema de Savitch." "" si k == 0 : devuelve s == t si k == 1 : devuelve s == t o ( s , t ) en aristas para u en vértices : si k_edge_path ( s , u , floor ( k / 2 )) y k_edge_path ( u , t , ceil ( k / 2 )): return True return False
Esta búsqueda se llama a sí misma a una profundidad de recursividad de O (log n ) niveles, cada uno de los cuales requiere O (log n ) bits para almacenar los argumentos de la función y las variables locales en ese nivel, por lo que el espacio total utilizado por el algoritmo es. Aunque se describió anteriormente en la forma de un programa en un lenguaje de alto nivel, el mismo algoritmo puede implementarse con el mismo espacio asintótico delimitado en una máquina de Turing .
La razón por la que este algoritmo implica el teorema es que cualquier lenguaje corresponde a un grafo dirigido cuyos vértices son los configuraciones de una máquina de Turing decidir la pertenencia a L . Para cada, este gráfico tiene una ruta desde la configuración inicial en la entrada x hasta la configuración de aceptación si y solo si. Por lo tanto, decidir la conectividad es suficiente para decidir la pertenencia a L , y mediante el algoritmo anterior esto se puede hacer en.
Corolarios
Algunos corolarios importantes del teorema incluyen:
- PSPACE = NPSPACE
- Esto se deriva directamente del hecho de que el cuadrado de una función polinomial sigue siendo una función polinomial. Se cree que no existe una relación similar entre las clases de complejidad de tiempo polinomial, P y NP , aunque esto sigue siendo una cuestión abierta .
- NL ⊆ L 2
- STCON está completo en NL , por lo que todos los lenguajes en NL también están en la clase de complejidad.
Ver también
Notas
Referencias
- Arora, Sanjeev ; Barak, Boaz (2009), Complejidad computacional. Un enfoque moderno , Cambridge University Press , ISBN 978-0-521-42426-4, Zbl 1193.68112
- Papadimitriou, Christos (1993), "Sección 7.3: El método de accesibilidad", Complejidad computacional (1ª ed.), Addison Wesley, págs. 149-150, ISBN 0-201-53082-1
- Savitch, Walter J. (1970), "Relaciones entre complejidades de cinta deterministas y no deterministas", Journal of Computer and System Sciences , 4 (2): 177-192, doi : 10.1016 / S0022-0000 (70) 80006-X , hdl : 10338.dmlcz / 120475
- Sipser, Michael (1997), "Sección 8.1: Teorema de Savitch", Introducción a la teoría de la computación , PWS Publishing, págs. 279-281 , ISBN 0-534-94728-X
enlaces externos
- Lance Fortnow, Fundamentos de la complejidad, Lección 18: Teorema de Savitch . Consultado el 09/09/09.
- Richard J. Lipton , Teorema de Savitch . Da un relato histórico sobre cómo se descubrió la prueba.