PSPACE

Este artículo o sección necesita referencias que aparezcan en una publicación acreditada. Busca fuentes: «PSPACE» – noticias · libros · académico · imágenes Este aviso fue puesto el 13 de octubre de 2022.

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 (${\displaystyle S(n)=a_{k}n^{k}+a_{k-1}n^{k-1}+\dots +a_{0}}$) 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.