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 , usando 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 . Éstas incluyen:
- REG = DSPACE ( O (1)) = NSPACE ( O (1)), donde REG es la clase de lenguajes regulares (el no determinismo no agrega poder 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 =
- EXPSPACE = NEXPSPACE =
El teorema de Immerman-Szelepcsényi establece que NSPACE ( s ( n )) está cerrado bajo complemento para cada función s ( n ) ≥ log n .
Otra generalización es ASPACE, definida con máquinas de Turing alternas .
Relación con otras clases de complejidad
DSPACE
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:
Hora
NSPACE también se puede utilizar para determinar la complejidad temporal de una máquina de Turing determinista mediante el siguiente teorema:
Si una lengua L se decide en el espacio S ( n ) (donde S ( n ) ≥ log n ) por una TM no determinista, entonces existe una constante C tal que L se decide en el tiempo O ( C S ( n ) ) por uno determinista. [2]
Limitaciones
La medida de la complejidad del espacio 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 . La razón es que DSPACE describe la complejidad espacial utilizada por las máquinas deterministas de Turing , 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 trata de representar computadoras reales. Por esta razón, NSPACE tiene una utilidad limitada para aplicaciones del mundo real.