NPSPACE

En teoría de la complejidad computacional, la clase de complejidad NPSPACE es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no determinista en espacio polinómico y tiempo ilimitado.

Por el teorema de Savitch, NPSPACE = PSPACE.

Definición formal

Al denotar con NSPACE(t(n)), el conjunto de todos los problemas que pueden ser resueltos con una máquina de Turing no determinista usando espacio O(t(n)) para alguna función t sobre el tamaño n de la entrada y sin límite de tiempo, se puede definir NPSPACE formalmente como^[1]​

${\displaystyle \mathbf {NPSPACE} =\bigcup _{k\in \mathbb {N} }\mathbf {NPSPACE} (n^{k}).}$ 

Sin embargo, al admitir no determinismo en la máquina de Turing no se agrega poder adicional dado que reutilizando el espacio, una máquina de Turing determinista puede simular una máquina no determinista, si bien esto puede tomar mucho más tiempo.^[2]​

Referencias

1. Arora & Barak (2009) p.81
2. Arora & Barak (2009) p.85

•   Datos: Q9048338