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 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 . É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 = NESPACIO( O (log  n ))
• CSL = NSPACE( O ( n )), donde CSL es la clase de lenguajes sensibles al contexto .
• ESPACIO P = ESPACIO NP = ${\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})}$
• ESPACIO EXP = ESPACIO NEXPS = ${\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 toda función s ( n ) ≥ log n .

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

Relación con otras clases de complejidad

ESPACIO

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 ) mediante 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 determinado con un algoritmo determinado . 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 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.) . Curso de Tecnología. págs. 303–304. ISBN 978-0-534-95097-2.
2. Goddard, Wayne (2008). Introducción a la teoría de la computación . Jones y Bartlett Publishers, Inc. pág. 183.ISBN _ 978-0-7637-4125-9.

enlaces externos

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