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.
Todos los problemas resolubles en tiempo polinómico con máquinas no deterministas (todos los problemas que están en NP) pueden resolverse en espacio polinómico, por lo tanto, PSPACE incluye NP y Co-NP.
PSPACE-completo ⊆ PSPACE En la primera línea hay tres inclusiones, y se sabe que NL ⊂ PSPACE, de manera que al menos una de las inclusiones es estricta, aunque aún no se ha descubierto cuál de ellas lo es.
Se sospecha que las tres son inclusiones estrictas.
Se sospecha también que la inclusión de la última línea es estricta.
Los problemas más difíciles en PSPACE son los del conjunto PSPACE-completo.
La adición de este operador hace distinguible el PSPACE del PH.
Debe ser capaz de convencer al verificador con una elevada probabilidad, si la cadena está en el lenguaje, pero no debería ser capaz de convencer con una baja probabilidad, si la cadena no está en el lenguaje.
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] 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.