ESPACIO

En la teoría de la complejidad computacional , DSPACE o ESPACIO es el recurso computacional que describe el recurso de espacio de memoria para una máquina de Turing determinista . Representa la cantidad total de espacio de memoria que una computadora física "normal" necesitaría para resolver un problema computacional determinado con un algoritmo determinado .

Clases de complejidad

La medida DSPACE se utiliza para definir clases de complejidad , conjuntos de todos los problemas de decisión que se pueden resolver utilizando una determinada cantidad de espacio de memoria. Para cada función f ( n ), existe una clase de complejidad ESPACIO ( f ( n ) ), el conjunto de problemas de decisión que pueden resolverse mediante una máquina de Turing determinista utilizando el espacio O ( f ( n )). No hay restricciones sobre la cantidad de tiempo de cálculo que se puede utilizar, aunque puede haber restricciones sobre algunas otras medidas de complejidad (como la alternancia ).

Varias clases de complejidad importantes se definen en términos de DSPACE . Éstas incluyen:

• REG = DSPACE( O (1)), donde REG es la clase de lenguajes regulares . De hecho, REG = DSPACE( o (log log  n )) (es decir, se requiere Ω(log log  n ) espacio para reconocer cualquier lenguaje no regular). ^{[1] [2]}

Prueba: Supongamos que existe un lenguaje no regular L ∈ DSPACE( s ( n ) ), para s ( n ) = o (log log n ). Sea M una máquina de Turing que decide L en el espacio s ( n ). Según nuestra suposición L ∉ DSPACE( O (1)); por lo tanto, para cualquier arbitrario , existe una entrada de M que requiere más espacio que k . ${\displaystyle k\in \mathbb {N} }$

Sea x una entrada de tamaño más pequeño, denotada por n, que requiere más espacio que k , y sea el conjunto de todas las configuraciones de M en la entrada x . Debido a que M ∈ DSPACE( s ( n )), entonces , donde c es una constante que depende de M. ${\displaystyle {\mathcal {C}}}$ ${\displaystyle |{\mathcal {C}}|\leq 2^{c.s(n)}=o(\log n)}$

Sea S el conjunto de todas las posibles secuencias de cruce de M en x . Tenga en cuenta que la longitud de una secuencia de cruce de M en x es como máximo : si es más larga que eso, entonces alguna configuración se repetirá y M entrará en un bucle infinito. También hay como máximo posibilidades para cada elemento de una secuencia de cruce, por lo que el número de secuencias de cruce diferentes de M en x es ${\displaystyle |{\mathcal {C}}|}$ ${\displaystyle |{\mathcal {C}}|}$

${\displaystyle |S|\leq |{\mathcal {C}}|^{|{\mathcal {C}}|}\leq (2^{c.s(n)})^{2^{c.s(n)}}=2^{c.s(n).2^{c.s(n)}}<2^{2^{2c.s(n)}}=2^{2^{o(\log \log n)}}=o(n)}$

Según el principio de casillero , existen índices i < j tales que , donde y son las secuencias de cruce en el límite i y j , respectivamente. ${\displaystyle {\mathcal {C}}_{i}(x)={\mathcal {C}}_{j}(x)}$ ${\displaystyle {\mathcal {C}}_{i}(x)}$ ${\displaystyle {\mathcal {C}}_{j}(x)}$

Sea x' la cadena obtenida de x eliminando todas las celdas de i + 1 a j . La máquina M todavía se comporta exactamente de la misma manera en la entrada x' que en la entrada x , por lo que necesita el mismo espacio para calcular x' que para calcular x . Sin embargo, | x' | < | x | , contradiciendo la definición de x . Por tanto, no existe el lenguaje L como se supone. □

El teorema anterior implica la necesidad del supuesto de función construible en el espacio en el teorema de la jerarquía espacial .

• L = DESPACIO( O (log  n ))
• ESPACIO = ${\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(n^{k})}$
• ESPACIO EXPRESO = ${\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(2^{n^{k}})}$

Modelos de maquina

DSPACE se mide tradicionalmente en una máquina determinista de Turing . Varias clases importantes de complejidad espacial son sublineales , es decir, más pequeñas que el tamaño de la entrada. Por lo tanto, "cargar" el algoritmo por el tamaño de la entrada o por el tamaño de la salida no capturaría realmente el espacio de memoria utilizado. Esto se resuelve definiendo la máquina de Turing multicinta con entrada y salida, que es una máquina de Turing multicinta estándar, excepto que nunca se puede escribir en la cinta de entrada y nunca se puede leer la cinta de salida. Esto permite definir clases de espacio más pequeñas, como L (espacio logarítmico), en términos de la cantidad de espacio utilizado por todas las cintas de trabajo (excluidas las cintas especiales de entrada y salida).

Dado que muchos símbolos pueden agruparse en uno tomando una potencia adecuada del alfabeto, para todo c ≥ 1 y f tales que f ( n ) ≥ 1 , la clase de lenguajes reconocibles en el espacio cf ( n ) es la misma que la clase de idiomas reconocibles en el espacio f ( n ). Esto justifica el uso de la notación O grande en la definición.

Teorema de jerarquía

El teorema de la jerarquía espacial muestra que, para cada función construible en el espacio , existe algún lenguaje L que es decidible en el espacio pero no en el espacio . ${\displaystyle f:\mathbb {N} \to \mathbb {N} }$ ${\displaystyle O(f(n))}$ ${\displaystyle o(f(n))}$

Relación con otras clases de complejidad

DSPACE es la contraparte determinista de NSPACE , la clase de espacio de memoria en una máquina de Turing no determinista . Por el teorema de Savitch , ^[3] tenemos que

${\displaystyle {\mathsf {DSPACE}}[s(n)]\subseteq {\mathsf {NSPACE}}[s(n)]\subseteq {\mathsf {DSPACE}}[(s(n))^{2}].}$

NTIME está relacionado con DSPACE de la siguiente manera. Para cualquierfunción construible en el tiempo t ( n ), tenemos

${\displaystyle {\mathsf {NTIME}}(t(n))\subseteq {\mathsf {DSPACE}}(t(n))}$.

Referencias

1. Szepietowski (1994) pág. 28
2. Alberts, Maris (1985), Complejidad espacial de las máquinas de Turing alternas
3. Arora y Barak (2009) pág. 86

• Szepietowski, Andrzej (1994). Máquinas de Turing con espacio sublogarítmico . Springer Ciencia + Medios comerciales . ISBN 978-3-540-58355-4.
• 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.

enlaces externos

• Zoológico de complejidad : DSPACE(f(n)).