NPSPACE

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]

${\displaystyle \mathbf {NPSPACE} =\bigcup _{k\in \mathbb {N} }\mathbf {NPSPACE} (n^{k}).}$

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.[2]