ESPACIO

En la teoría de la complejidad computacional , el espacio no determinista o NSPACE es el recurso computacional que describe el espacio de memoria para una máquina de Turing no determinista . Es la contraparte no determinista de DSPACE .

Clases de complejidad

La medida NSPACE se utiliza para definir la clase de complejidad cuyas soluciones pueden ser determinadas por una máquina de Turing no determinista . La clase de complejidad NSPACE( f ( n )) es el conjunto de problemas de decisión que pueden ser resueltos por una máquina de Turing no determinista , M , utilizando un espacio O ( f ( n )), donde n es la longitud de la entrada. ^{[ 1 ]}

En términos de NSPACE , se pueden definir varias clases de complejidad importantes . Estas incluyen:

REG = DSPACE( O (1)) = NSPACE( O (1)), donde REG es la clase de lenguajes regulares (el no determinismo no agrega potencia en espacio constante).
NL = NSPACE( O (log n ))
CSL = NSPACE( O ( n )), donde CSL es la clase de lenguajes sensibles al contexto .
ESPACIO P = ESPACIO NP = $\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})$
ESPACIO EXP = ESPACIO NEXP = $\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})$

El teorema de Immerman–Szelepcsényi establece que NSPACE( s ( n )) es cerrado bajo el complemento para toda función $s (n) \geq log n .$

Una generalización adicional es ASPACE, definida con máquinas de Turing alternas .

Relación con otras clases de complejidad

ESPACIO D

NSPACE es la contraparte no determinista de DSPACE , la clase de espacio de memoria en una máquina de Turing determinista . Primero por definición, y luego por el teorema de Savitch , tenemos que:

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

Tiempo

NSPACE también se puede utilizar para acotar la complejidad temporal determinista de un problema, mediante el siguiente teorema:

Si un lenguaje L es decidido en un espacio S ( n ) (donde S ( n ) ≥ log n ) por una máquina de Turing no determinista, entonces existe una constante C tal que L es decidido en un tiempo O ( C ^{S ( n )} ) por una determinista. ^{[ 2 ]}

Limitaciones

La medida de complejidad espacial en términos de DSPACE es útil porque representa la cantidad total de memoria que una computadora real necesitaría para resolver un problema computacional dado con un algoritmo dado . Esto se debe a que DSPACE describe la complejidad espacial utilizada por las máquinas de Turing deterministas , que pueden representar computadoras reales. Por otro lado, NSPACE describe la complejidad espacial de las máquinas de Turing no deterministas , que no son útiles al intentar representar computadoras reales. Por esta razón, la utilidad de NSPACE se limita a aplicaciones del mundo real.

Referencias

↑ Sipser, Michael (2006). Introducción a la teoría de la computación (2.ª ed.) . Course Technology. pp. 303–304 . ISBN 978-0-534-95097-2.
↑ Goddard, Wayne (2008). Introducción a la teoría de la computación . Jones and Bartlett Publishers, Inc. pág. 183. ISBN 978-0-7637-4125-9.

Enlaces externos

Zoológico de complejidad : NSPACE( f ( n )) .

[1] Sipser, Michael (2006). Introducción a la teoría de la computación (2.ª ed.) . Course Technology. pp. 303–304 . ISBN 978-0-534-95097-2.

[2] Goddard, Wayne (2008). Introducción a la teoría de la computación . Jones and Bartlett Publishers, Inc. pág. 183. ISBN 978-0-7637-4125-9.

[ 1 ]

[ 2 ]