En la teoría de la complejidad computacional , los teoremas de la jerarquía espacial son resultados de separación que muestran que tanto las máquinas deterministas como las no deterministas pueden resolver más problemas en (asintóticamente) más espacio, sujeto a ciertas condiciones. Por ejemplo, una máquina de Turing determinista puede resolver más problemas de decisión en el espacio n log n que en el espacio n . Los teoremas análogos algo más débiles para el tiempo son los teoremas de jerarquía temporal .
El fundamento de los teoremas de la jerarquía radica en la intuición de que con más tiempo o más espacio viene la capacidad de calcular más funciones (o decidir más lenguajes). Los teoremas de la jerarquía se utilizan para demostrar que las clases de complejidad temporal y espacial forman una jerarquía en la que las clases con límites más estrictos contienen menos lenguajes que aquellas con límites más relajados. Aquí definimos y probamos el teorema de la jerarquía espacial.
Los teoremas de la jerarquía espacial se basan en el concepto de funciones construibles en el espacio . Los teoremas de la jerarquía espacial determinista y no determinista establecen que para todas las funciones construibles en el espacio f ( n ),
- ,
donde el espacio es sinónimo de bien DSPACE o NSPACE , y O se refiere a la poca o notación.
Declaración
Formalmente, una función es construible en el espacio si y existe una máquina de Turing que calcula la función en el espacio al comenzar con una entrada , dónde representa una cadena de n 1 consecutivos. La mayoría de las funciones comunes con las que trabajamos son construibles en el espacio, incluidos polinomios, exponentes y logaritmos.
Para cada función de construcción espacial , existe un lenguaje L que es decidible en el espacio pero no en el espacio .
Prueba
El objetivo aquí es definir un lenguaje que se pueda decidir en el espacio. pero no espacio . Aquí definimos el lenguaje L :
Ahora, para cualquier máquina M que decida un idioma en el espacio, L diferirá en al menos un punto de la lengua de M . Es decir, para algunos k suficientemente grandes, M usará espacio en y por lo tanto diferirá en su valor.
Por otro lado, L está en. El algoritmo para decidir el idioma L es el siguiente:
- En una entrada x , calcule usando el espacio-constructibilidad y marcando celdas de cinta. Siempre que se intente utilizar más decélulas, rechazar .
- Si x no tiene la formapara algunos TM M , rechazar .
- Simular M en la entrada x como máximo pasos (usando espacio). Si la simulación intenta utilizar más de espacio o más de operaciones, luego rechazar .
- Si M aceptó x durante esta simulación, entonces rechace ; de lo contrario, acepta .
Nota sobre el paso 3: la ejecución se limita a pasos para evitar el caso en el que M no se detiene en la entrada x . Es decir, el caso en el que M consume espacio de solo según sea necesario, pero se ejecuta durante un tiempo infinito.
La prueba anterior es válida para el caso de PSPACE, mientras que debemos hacer algún cambio para el caso de NPSPACE. El punto crucial es que mientras en una MT determinista podemos fácilmente invertir la aceptación y el rechazo (crucial para el paso 4), esto no es posible en una máquina no determinista.
Para el caso de NPSPACE, primero redefiniremos L :
Ahora, necesitamos cambiar el algoritmo para aceptar L modificando el paso 4 a:
- Si M aceptó x durante esta simulación, entonces acepte ; de lo contrario, rechace .
Ahora demostraremos por contradicción que L no puede ser decidido por una TM usandocélulas. Suponiendo que L puede ser decidido por algún TM M usandocélulas, y siguiendo el teorema de Immerman-Szelepcsényi , también puede ser determinado por una TM (que llamaremos ) utilizando células. Aquí radica la contradicción, por lo tanto, nuestra suposición debe ser falsa:
- Si (para algunos k suficientemente grandes) no está en entonces M lo aceptará, por lo tantorechaza w , por lo tanto, w está en (contradicción).
- Si (para algunos k suficientemente grandes) está en entonces M lo rechazará, por lo tantoacepta w , por lo tanto, w no está en (contradicción).
Comparación y mejoras
El teorema de la jerarquía espacial es más fuerte que los teoremas análogos de la jerarquía temporal de varias formas:
- Solo requiere que s (n) sea al menos log n en lugar de al menos n .
- Puede separar clases con cualquier diferencia asintótica, mientras que el teorema de la jerarquía temporal requiere que estén separadas por un factor logarítmico.
- Solo requiere que la función sea construible en el espacio, no en el tiempo.
Parece ser más fácil separar clases en el espacio que en el tiempo. De hecho, mientras que el teorema de la jerarquía temporal ha experimentado pocas mejoras notables desde su inicio, el teorema de la jerarquía espacial no determinista ha visto al menos una mejora importante de Viliam Geffert en su artículo de 2003 "Teorema de la jerarquía espacial revisado". Este artículo hizo varias generalizaciones del teorema:
- Relaja el requisito de espacio-constructibilidad. En lugar de simplemente separar las clases sindicales y , se separa de dónde es un arbitrario función y g (n) es un computable función. Estas funciones no necesitan ser construibles en el espacio o incluso aumentar monótonamente.
- Identifica un lenguaje unario , o lenguaje de conteo, que pertenece a una clase pero no a la otra. En el teorema original, el lenguaje de separación era arbitrario.
- No requiere ser al menos log n ; puede ser cualquier función no determinista y completamente construible en el espacio.
Refinamiento de la jerarquía espacial
Si el espacio se mide como el número de celdas utilizadas independientemente del tamaño del alfabeto, entonces porque se puede lograr cualquier compresión lineal cambiando a un alfabeto más grande. Sin embargo, midiendo el espacio en bits, se puede lograr una separación mucho más nítida para el espacio determinista. En lugar de definirse hasta una constante multiplicativa, el espacio ahora se define hasta una constante aditiva. Sin embargo, debido a que se puede ahorrar cualquier cantidad constante de espacio externo almacenando el contenido en el estado interno, todavía tenemos.
Suponga que f es construible en el espacio. EL ESPACIO es determinista.
- Para una amplia variedad de modelos computacionales secuenciales, incluso para máquinas de Turing, SPACE ( f ( n ) - ω (log ( f ( n ) + n ))) ⊊ SPACE ( f ( n )). Esto es válido incluso si SPACE ( f ( n ) - ω (log ( f ( n ) + n ))) se define utilizando un modelo computacional diferente al porque los diferentes modelos pueden simularse entre sí con espacio arriba.
- Para ciertos modelos computacionales, incluso tenemos ESPACIO ( f ( n ) - ω (1)) ⊊ ESPACIO ( f ( n )). En particular, esto es válido para las máquinas de Turing si arreglamos el alfabeto, el número de cabezas en la cinta de entrada, la cantidad de cabezas en la cinta de trabajo (usando una sola cinta de trabajo) y agregamos delimitadores para la parte visitada de la cinta de trabajo (que puede comprobar sin aumentar el uso del espacio). ESPACIO ( f ( n )) no depende de si la cinta de trabajo es infinita o semiinfinita. También podemos tener un número fijo de cintas de trabajo si f ( n ) es una tupla construible SPACE que da el uso de espacio por cinta, o un SPACE ( f ( n ) - ω (log ( f ( n ))) - número construible dando el uso total del espacio (sin contar los gastos generales para almacenar la longitud de cada cinta).
La demostración es similar a la demostración del teorema de la jerarquía espacial, pero con dos complicaciones: la máquina de Turing universal debe ser eficiente en el espacio y la inversión debe ser eficiente en el espacio. Generalmente se pueden construir máquinas de Turing universales con espacio por encima de la cabeza, y bajo supuestos apropiados, sólo espacio superior (que puede depender de la máquina que se está simulando). Para la inversión, la cuestión clave es cómo detectar si la máquina simulada rechaza ingresando en un bucle infinito (con espacio limitado). Contar simplemente el número de pasos dados aumentaría el consumo de espacio en aproximadamente. A costa de un aumento de tiempo potencialmente exponencial, los bucles se pueden detectar de manera eficiente en el espacio de la siguiente manera: [1]
Modifique la máquina para borrar todo y pasar a una configuración específica A en caso de éxito. Utilice la búsqueda en profundidad para determinar si se puede alcanzar A en el espacio limitado desde la configuración inicial. La búsqueda comienza en A y repasa las configuraciones que conducen a A. Debido al determinismo, esto se puede hacer en el lugar y sin entrar en un bucle.
También podemos determinar si la máquina excede un límite de espacio (en lugar de hacer un bucle dentro del límite de espacio) iterando sobre todas las configuraciones a punto de exceder el límite de espacio y verificando (nuevamente usando la búsqueda en profundidad) si la configuración inicial conduce a alguno de ellos.
Corolarios
Corolario 1
Para dos funciones cualesquiera , , dónde es y es construible en el espacio, .
Este corolario nos permite separar varias clases de complejidad espacial. Para cualquier funciónes construible en el espacio para cualquier número natural k. Por lo tanto, para dos números naturales cualesquiera podemos probar . Podemos extender esta idea para números reales en el siguiente corolario. Esto demuestra la jerarquía detallada dentro de la clase PSPACE.
Corolario 2
Para dos números reales no negativos cualesquiera .
Corolario 3
Prueba
El teorema de Savitch muestra que, mientras que el teorema de la jerarquía espacial muestra que . Por lo tanto, obtenemos este corolario junto con el hecho de que TQBF ∉ NL ya que TQBF es PSPACE-complete.
Esto también podría probarse usando el teorema de la jerarquía espacial no determinista para mostrar que NL ⊊ NPSPACE, y usando el teorema de Savitch para mostrar que PSPACE = NPSPACE.
Corolario 4
Este último corolario muestra la existencia de problemas decidibles que son insolubles. En otras palabras, sus procedimientos de decisión deben usar más que espacio polinomial.
Corolario 5
Hay problemas en PSPACE que requieren un exponente arbitrariamente grande para resolver; por lo tanto, PSPACE no colapsa a DSPACE ( n k ) para alguna constante k .
Ver también
Referencias
- ^ Sipser, Michael (1978). "Detener cálculos delimitados por el espacio". Actas del XIX Simposio anual sobre fundamentos de la informática .
- Arora, Sanjeev ; Barak, Boaz (2009). Complejidad computacional. Un enfoque moderno . Prensa de la Universidad de Cambridge . ISBN 978-0-521-42426-4. Zbl 1193.68112 .
- Luca Trevisan . Notas sobre teoremas de jerarquía . Folleto 7. CS172: Autómatas, computabilidad y complejidad. UC Berkeley. 26 de abril de 2004.
- Viliam Geffert . Teorema de la jerarquía espacial revisado . Ciencias de la Computación Teórica , volumen 295, número 1-3, p. 171-187. 24 de febrero de 2003.
- Sipser, Michael (1997). Introducción a la Teoría de la Computación . Publicación de PWS. ISBN 0-534-94728-X. Páginas 306–310 de la sección 9.1: Teoremas de jerarquía.
- Papadimitriou, Christos (1993). Complejidad computacional (1ª ed.). Addison Wesley. ISBN 0-201-53082-1. Sección 7.2: El teorema de la jerarquía, págs. 143-146.