Se sospecha ampliamente que estos problemas pueden estar fuera de las conocidas clases de complejidad P y NP, pero no es un hecho que haya sido demostrado.
Este problema trata de descubrir si hay variables a las que al asignarle el valor verdadero convierten una expresión booleana en verdadera.
Algunos ejemplos de juegos que sean PSPACE-completos (cuando están generalizados de manera que se pueda jugar en un tablero de dimensión n x n) son los juegos hex y reversi y los juegos en solitario Solitario Mahjong, Atomix, Sokoban.
Resaltaremos también que la definición de PSPACE-completitud está basada en la complejidad asintótica: el tiempo que tarda en resolverse un problema de tamaño n cuando n crece sin ningún límite.
Esto quiere decir que un juego como las damas (que se juega en un tablero de 8 x 8) nunca podrá ser PSPACE-completo (de hecho, puede ser resuelto en un tiempo constante utilizando una enorme Lookup table).
El problema de la Geografía Generalizada es un juego infantil similar a las palabras encadenadas pero empleando únicamente ciudades que deban empezar con el nombre de la anterior sin repetir ninguna.