Espacio Nacional

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 determinarse mediante una máquina de Turing no determinista . La clase de complejidad NSPACE( f ( n )) es el conjunto de problemas de decisión que pueden resolverse mediante una máquina de Turing no determinista , M , utilizando el espacio O ( f ( n )), donde n es la longitud de la entrada. ^[1]

Se pueden definir varias clases de complejidad importantes en términos de NSPACE . Entre ellas se incluyen:

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

El teorema de Immerman–Szelepcsényi establece que NSPACE( s ( n )) es cerrado bajo complemento para cada función s ( n ) ≥ 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, luego por el teorema de Savitch , tenemos que:

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

Tiempo

NSPACE también se puede utilizar para determinar la complejidad temporal de una máquina de Turing determinista mediante el siguiente teorema:

Si un lenguaje L se decide en el espacio S ( n ) (donde S ( n ) ≥ log n ) por una MT no determinista, entonces existe una constante C tal que L se decide en el tiempo O ( C ^{S ( n )} ) por una determinista. ^[2]

Limitaciones

La medida de la complejidad espacial en términos de DSPACE es útil porque representa la cantidad total de memoria que necesitaría una computadora real para resolver un problema computacional determinado con un algoritmo determinado . La razón es 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 cuando se intenta representar computadoras reales. Por esta razón, NSPACE tiene una utilidad limitada para aplicaciones del mundo real.

Referencias

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.

Enlaces externos

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