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.
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
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.
Escribe un comentario o lo que quieras sobre NPSPACE (directo, no tienes que registrarte)
Comentarios
(de más nuevos a más antiguos)