Teorema de la jerarquía espacial

Tanto las máquinas deterministas como las no deterministas pueden resolver más problemas si se les da más espacio.

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 .

La base de los teoremas de la jerarquía reside en la intuición de que con más tiempo o más espacio surge la capacidad de calcular más funciones (o decidir más lenguajes). Los teoremas de jerarquía se utilizan para demostrar que las clases de complejidad temporal y espacial forman una jerarquía donde las clases con límites más estrictos contienen menos idiomas que aquellas con límites más relajados. Aquí definimos y demostramos 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 jerarquía espacial determinista y no determinista establecen que para todas las funciones construibles en el espacio f ( n ),

${\displaystyle {\mathsf {SPACE}}\left(o(f(n))\right)\subsetneq {\mathsf {SPACE}}(f(n))}$,

donde SPACE significa DSPACE o NSPACE y o se refiere a la pequeña notación o.

Declaración

Formalmente, una función es construible en el espacio si existe una máquina de Turing que calcula la función en el espacio cuando comienza con una entrada , donde representa una cadena de n unos consecutivos. La mayoría de las funciones comunes con las que trabajamos son construibles en el espacio, incluidos polinomios, exponentes y logaritmos. ${\displaystyle f:\mathbb {N} \longrightarrow \mathbb {N} }$ ${\displaystyle f(n)\geq \log ~n}$ ${\displaystyle f(n)}$ ${\displaystyle O(f(n))}$ ${\displaystyle 1^{n}}$ ${\displaystyle 1^{n}}$

Para cada función construible en el espacio , existe un lenguaje L que es decidible en el espacio pero no en el espacio . ${\displaystyle f:\mathbb {N} \longrightarrow \mathbb {N} }$ ${\displaystyle O(f(n))}$ ${\displaystyle o(f(n))}$

Prueba

El objetivo es definir un lenguaje que pueda decidirse en el espacio pero no en el espacio . El lenguaje se define como L : ${\displaystyle O(f(n))}$ ${\displaystyle o(f(n))}$

${\displaystyle L=\{~(\langle M\rangle ,10^{k}):M{\mbox{ uses space }}\leq f(|\langle M\rangle ,10^{k}|){\mbox{ and time }}\leq 2^{f(|\langle M\rangle ,10^{k}|)}{\mbox{ and }}M{\mbox{ does not accept }}(\langle M\rangle ,10^{k})~\}}$

Para cualquier máquina M que decida un lenguaje en el espacio , L diferirá en al menos un punto del lenguaje de M. Es decir, para algunos k lo suficientemente grandes , M utilizará espacio y , por lo tanto, diferirá en su valor. ${\displaystyle o(f(n))}$ ${\displaystyle \leq f(|\langle M\rangle ,10^{k}|)}$ ${\displaystyle (\langle M\rangle ,10^{k})}$

Por otro lado, L está en . El algoritmo para decidir el idioma L es el siguiente: ${\displaystyle {\mathsf {SPACE}}(f(n))}$

1. En una entrada x , calcule utilizando la constructibilidad del espacio y marque las celdas de la cinta. Siempre que se intente utilizar más de celdas, rechace . ${\displaystyle f(|x|)}$ ${\displaystyle f(|x|)}$ ${\displaystyle f(|x|)}$
2. Si x no tiene la forma de algún TMM , rechace . ${\displaystyle \langle M\rangle ,10^{k}}$
3. Simule M en la entrada x para la mayoría de los pasos (usando espacio). Si la simulación intenta utilizar más que espacio o más que operaciones, entonces rechace . ${\displaystyle 2^{f(|x|)}}$ ${\displaystyle f(|x|)}$ ${\displaystyle f(|x|)}$ ${\displaystyle 2^{f(|x|)}}$
4. Si M aceptó x durante esta simulación, entonces rechace ; en caso contrario, acepte .

Nota sobre el paso 3: La ejecución se limita a los 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 sólo según sea necesario, pero se ejecuta durante un tiempo infinito. ${\displaystyle 2^{f(|x|)}}$ ${\displaystyle O(f(x))}$

La prueba anterior es válida para el caso de PSPACE, pero es necesario realizar algunos cambios para el caso de NPSPACE. El punto crucial es que, mientras que en una TM determinista la aceptación y el rechazo se pueden invertir (crucial para el paso 4), esto no es posible en una máquina no determinista.

Para el caso de NPSPACE, primero es necesario redefinir L :

${\displaystyle L=\{~(\langle M\rangle ,10^{k}):M{\mbox{ uses space }}\leq f(|\langle M\rangle ,10^{k}|){\mbox{ and }}M{\mbox{ accepts }}(\langle M\rangle ,10^{k})~\}}$

Ahora, es necesario cambiar el algoritmo para aceptar L modificando el paso 4 para:

• Si M aceptó x durante esta simulación, entonces acepte ; en caso contrario, rechace .

L no puede ser decidido por una TM usando celdas. Suponiendo que L puede decidirse mediante alguna TM M usando celdas, y siguiendo el teorema de Immerman-Szelepcsényi , también puede determinarse mediante una TM (llamada ) usando celdas. Aquí radica la contradicción, por lo tanto la suposición debe ser falsa: ${\displaystyle o(f(n))}$ ${\displaystyle o(f(n))}$ ${\displaystyle {\overline {L}}}$ ${\displaystyle {\overline {M}}}$ ${\displaystyle o(f(n))}$

1. Si (para algo k lo suficientemente grande ) no está en entonces M lo aceptará, por lo tanto rechaza w , por lo tanto w está en (contradicción). ${\displaystyle w=(\langle {\overline {M}}\rangle ,10^{k})}$ ${\displaystyle {\overline {L}}}$ ${\displaystyle {\overline {M}}}$ ${\displaystyle {\overline {L}}}$
2. Si (para algo k lo suficientemente grande ) está en entonces M lo rechazará, por lo tanto acepta w , por lo tanto w no está en (contradicción). ${\displaystyle w=(\langle {\overline {M}}\rangle ,10^{k})}$ ${\displaystyle {\overline {L}}}$ ${\displaystyle {\overline {M}}}$ ${\displaystyle {\overline {L}}}$

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 en varios sentidos:

• 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.
• Sólo requiere que la función sea construible en el espacio, no en el tiempo.

Parece 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 experimentado al menos una mejora importante por parte 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 constructibilidad del espacio. En lugar de simplemente separar las clases de unión y , se separa de donde hay una función arbitraria y g(n) es una función computable . Estas funciones no tienen por qué ser construibles en el espacio ni siquiera monótonas y crecientes. ${\displaystyle {\mathsf {DSPACE}}(O(s(n))}$ ${\displaystyle {\mathsf {DSPACE}}(o(s(n))}$ ${\displaystyle {\mathsf {DSPACE}}(f(n))}$ ${\displaystyle {\mathsf {DSPACE}}(g(n))}$ ${\displaystyle f(n)}$ ${\displaystyle O(s(n))}$ ${\displaystyle o(s(n))}$
• Identifica un lenguaje unario , o lenguaje de cuenta, que está en una clase pero no en la otra. En el teorema original, el lenguaje de separación era arbitrario.
• No es necesario que sea al menos log n ; puede ser cualquier función no determinista y totalmente construible en el espacio. ${\displaystyle s(n)}$

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 se puede lograr cualquier compresión lineal cambiando a un alfabeto más grande. Sin embargo, al medir 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 una cantidad constante de espacio externo almacenando el contenido en el estado interno, todavía tenemos . ${\displaystyle {\mathsf {SPACE}}(f(n))={\mathsf {SPACE}}(O(f(n)))}$ ${\displaystyle {\mathsf {SPACE}}(f(n))={\mathsf {SPACE}}(f(n)+O(1))}$

Supongamos que f es construible en el espacio. EL ESPACIO es determinista.

• Para una amplia variedad de modelos computacionales secuenciales, incluidas las máquinas de Turing, ESPACIO ( f ( n )- ω (log( f ( n )+ n ))) ⊊ ESPACIO( f ( n )). Esto es válido incluso si SPACE( f ( n )- ω (log( f ( n )+ n ))) se define utilizando un modelo computacional diferente porque los diferentes modelos pueden simularse entre sí con espacio adicional. ${\displaystyle {\mathsf {SPACE}}(f(n))}$ ${\displaystyle O(\log(f(n)+n))}$
• 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 fijamos el alfabeto, el número de cabezas en la cinta de entrada, el número 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 comprobarse sin aumentar el uso de 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 proporciona el uso de espacio por cinta, o un número construible SPACE( f ( n )- ω (log( f ( n ))) dando el uso total del espacio (sin contar los gastos generales para almacenar la longitud de cada cinta).

La prueba es similar a la prueba del teorema de la jerarquía espacial, pero con dos complicaciones: la máquina universal de Turing tiene que ser eficiente en el espacio, y la inversión tiene que ser eficiente en el espacio. Generalmente se pueden construir máquinas de Turing universales con espacio sobre la cabeza y, bajo suposiciones apropiadas, solo espacio sobre la cabeza (lo que puede depender de la máquina que se esté simulando). Para la reversión, la cuestión clave es cómo detectar si la máquina simulada rechaza ingresando en un bucle infinito (con espacio limitado). Simplemente contar 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 forma eficiente desde el punto de vista espacial de la siguiente manera: ^[1] ${\displaystyle O(\log(space))}$ ${\displaystyle O(1)}$ ${\displaystyle f(n)}$

Modifique la máquina para borrar todo y vaya a una configuración A específica en caso de éxito. Utilice la búsqueda en profundidad para determinar si se puede acceder a A en el espacio limitado desde la configuración inicial. La búsqueda comienza en A y recorre las configuraciones que conducen a A. Debido al determinismo, esto se puede hacer en el lugar y sin entrar en un bucle.

También se puede 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 búsqueda en profundidad) si la configuración inicial conduce a algún límite. de ellos.

Corolarios

Corolario 1

Para dos funciones cualesquiera , , donde es y es construible en el espacio, . ${\displaystyle f_{1}}$ ${\displaystyle f_{2}:\mathbb {N} \longrightarrow \mathbb {N} }$ ${\displaystyle f_{1}(n)}$ ${\displaystyle o(f_{2}(n))}$ ${\displaystyle f_{2}}$ ${\displaystyle {\mathsf {SPACE}}(f_{1}(n))\subsetneq {\mathsf {SPACE}}(f_{2}(n))}$

Este corolario nos permite separar varias clases de complejidad espacial. Para cualquier número natural k, la función es construible en el espacio. Por lo tanto, para dos números naturales cualesquiera podemos demostrar . ${\displaystyle n^{k}}$ ${\displaystyle k_{1}<k_{2}}$ ${\displaystyle {\mathsf {SPACE}}(n^{k_{1}})\subsetneq {\mathsf {SPACE}}(n^{k_{2}})}$

Corolario 2

NL ⊊ ESPACIO .

Prueba

El teorema de Savitch muestra que , mientras que el teorema de la jerarquía espacial muestra que . El resultado es este corolario junto con el hecho de que TQBF ∉ NL ya que TQBF es PSPACE-completo. ${\displaystyle {\mathsf {NL}}\subseteq {\mathsf {SPACE}}(\log ^{2}n)}$ ${\displaystyle {\mathsf {SPACE}}(\log ^{2}n)\subsetneq {\mathsf {SPACE}}(n)}$

Esto también podría probarse usando el teorema de jerarquía espacial no determinista para mostrar que NL ⊊ NPSPACE, y usando el teorema de Savitch para mostrar que PSPACE = NPSPACE.

Corolario 3

ESPACIO P ⊊ ESPACIO EXP .

Este último corolario muestra la existencia de problemas decidibles que son intratables. En otras palabras, sus procedimientos de decisión deben utilizar más que el espacio polinómico.

Corolario 4

Hay problemas en PSPACE que requieren un exponente arbitrariamente grande para resolverse; por lo tanto, PSPACE no colapsa en DSPACE ( n ^k ) para alguna constante k .

Corolario 5

ESPACIO( n ) ≠ PTIME .

Para verlo, supongamos lo contrario, así cualquier problema decidido en el espacio se decide en el tiempo , y cualquier problema decidido en el espacio se decide en el tiempo . Ahora bien , entonces P está cerrado bajo tal cambio de límite, es decir , entonces . Esto implica que para todos , pero el teorema de la jerarquía espacial implica que , y se sigue el Corolario 6. Nótese que este argumento no prueba ni eso ni que , como para llegar a una contradicción usamos la negación de ambas oraciones, es decir usamos ambas inclusiones, y solo podemos deducir que al menos una falla. Actualmente se desconoce cuáles fallan, pero se conjetura que ambas fallan, es decir, y son incomparables, al menos para el espacio determinista. ^[2] Esta pregunta está relacionada con la de la complejidad temporal de los autómatas lineales acotados (no deterministas) que aceptan la clase de complejidad (también conocida como lenguajes sensibles al contexto , CSL); por lo tanto, según el CSL anterior, no se sabe que sea decidible en tiempo polinomial; consulte también los dos problemas de Kuroda en LBA . ${\displaystyle O(n)}$ ${\displaystyle O(n^{c})}$ ${\displaystyle L}$ ${\displaystyle O(n^{b})}$ ${\displaystyle O((n^{b})^{c})=O(n^{bc})}$ ${\displaystyle {\mathsf {P}}:=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}(n^{k})}$ ${\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}(n^{bk})\subseteq {\mathsf {P}}}$ ${\displaystyle L\in {\mathsf {P}}}$ ${\displaystyle b,{\mathsf {SPACE}}(n^{b})\subseteq {\mathsf {P}}\subseteq {\mathsf {SPACE}}(n)}$ ${\displaystyle {\mathsf {SPACE}}(n^{2})\not \subseteq {\mathsf {SPACE}}(n)}$ ${\displaystyle {\mathsf {P}}\not \subseteq {\mathsf {SPACE}}(n)}$ ${\displaystyle {\mathsf {SPACE}}(n)\not \subseteq {\mathsf {P}}}$ ${\displaystyle {\mathsf {SPACE}}(n)}$ ${\displaystyle {\mathsf {P}}}$ ${\displaystyle {\mathsf {NSPACE}}(n)}$

Ver también

• Teorema de la jerarquía del tiempo

Referencias

1. Sipser, Michael (1978). "Detener los cálculos limitados al espacio". Actas del 19º Simposio Anual sobre Fundamentos de la Informática .
2. "¿Cómo sabemos que P! = LINSPACE sin saber si uno es un subconjunto del otro?".

• Arora, Sanjeev ; Barac, Booz (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. Informática 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 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.