Article · Español
En teoría de la complejidad computacional, la clase PSPACE es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing determinista en espacio de polinomios y tiempo ilimitado. La definición no depende del carácter determinista de la máquina de Turing (esto es un corolario del teorema de Savitch). De manera que PSPACE = NPSPACE. Si un problema se resuelve mediante un algoritmo no determinista de complejidad espacial polinómica, también se puede resolver mediante un algoritmo determinista de complejidad espacial polinómica.
Abstract from DBpedia / Wikipedia · CC BY-SA