Dicho de otra forma, existe un algoritmo que trabaja en tiempo polinómico que transforma las instancias de un problema en las instancias del otro con la misma respuesta.
EXPSPACE contiene de forma estricta las clases PSPACE, NP-completo, NP y P y se cree que también contiene estrictamente el conjunto EXPTIME.
Un ejemplo de problema en EXPSPACE-completo es el de decidir si dos expresiones regulares representan lenguajes diferentes, cuando los operadores regulares utilizados son la unión, la concatenación, la clausura de Kleene (cero o más copias de una expresión), y el cuadrado (dos copias de una expresión).
Si no se incluye la clausura de Kleene, el problema es NEXPTIME-completo, que es como EXPTIME-completo, salvo que se define según las máquinas de Turing no-deterministas.
En 1980, L. Berman demostró que el problema de verificar o falsificar cualquier expresión de primer orden sobre los números reales que solo utiliza suma y comparación (pero no multiplicación) está en EXPSPACE.