Espacio D

En la teoría de la complejidad computacional , DSPACE o SPACE 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 necesitaría una computadora física "normal" 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 cierta cantidad de espacio de memoria. Para cada función f ( n ), existe una clase de complejidad SPACE( f ( n )), el conjunto de problemas de decisión que se pueden resolver mediante una máquina de Turing determinista utilizando el espacio O ( f ( n )). No hay ninguna restricción en la cantidad de tiempo de cálculo que se puede utilizar, aunque puede haber restricciones en algunas otras medidas de complejidad (como la alternancia ).

En términos de DSPACE se definen varias clases de complejidad importantes , entre ellas:

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

Demostración: 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 ). Por nuestra suposición L ∉ DSPACE( O (1)); por lo tanto, para cualquier , 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ínimo, denotada por n, que requiere más espacio que k , y sea el conjunto de todas las configuraciones de M en la entrada x . Como 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 sobre x . Nótese que la longitud de una secuencia de cruce de M sobre 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 sobre 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 del palomar , existen índices i < j tales que , donde y son las secuencias de cruce en los límites 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 a partir de x eliminando todas las celdas desde i + 1 hasta j . La máquina M sigue comportándose exactamente de la misma manera con la entrada x' que con la entrada x , por lo que necesita el mismo espacio para calcular x' que para calcular x . Sin embargo, | x' | < | x | , lo que contradice la definición de x . Por lo tanto, no existe un lenguaje L como el que se supone. □

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

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

Modelos de máquinas

El DSPACE se mide tradicionalmente en una máquina de Turing determinista . Varias clases de complejidad espacial importantes 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 verdaderamente el espacio de memoria utilizado. Esto se soluciona definiendo la máquina de Turing multicinta con entrada y salida, que es una máquina de Turing multicinta estándar, excepto que la cinta de entrada nunca puede escribirse y la cinta de salida nunca puede leerse. Esto permite que las clases de espacio más pequeñas, como L (espacio logarítmico), se definan en términos de la cantidad de espacio utilizado por todas las cintas de trabajo (excluyendo las cintas especiales de entrada y salida).

Dado que muchos símbolos pueden empaquetarse en uno solo tomando una potencia adecuada del alfabeto, para todos los c ≥ 1 y f tales que f ( n ) ≥ 1 , la clase de idiomas 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 mayúscula en la definición.

Teorema de jerarquía

El teorema de 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 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 Science+Business Media . ISBN 978-3-540-58355-4.
• Arora, Sanjeev ; Barak, Boaz (2009). Complejidad computacional. Un enfoque moderno . Cambridge University Press . ISBN 978-0-521-42426-4.Zbl 1193.68112  .

Enlaces externos

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