En teoria de la complexitat, la classe de complexitat NSPACE(f(n)) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing no determinista en espai O(f(n)) i temps il·limitat. Es la contrapartida no determinista de la classe DSPACE.
Diverses classe de complexitat es defineixen en funció de DSPACE:
REG = DSPACE(O(1)) = NSPACE(O(1)). NL = NSPACE(O(log n)) CSL = NSPACE(O(n)), on CSL és la classe dels llenguatges sensibles al context PSPACE = NPSPACE = EXPSPACE = NEXPSPACE =
Una generalització d'aquesta classe és ASPACE, que es defineix amb màquines de Turing alternants.
Relació amb d'altres classes NSPACE és la contrapart no determinista de DSPACE, per la mateixa definició i pel teorema de Savitch es te:NSPACE es pot fer servir per determinar la complexitat temporal d'una màquina de Turing determinista pel següent teorema:Si un llenguatge L és dedicible en espai S(n) (on S(n) ≥ log n) per una màquina de Turing no determinista, llavors existeix una constant C tal que L és decidible en temps O(CS(n)) per una màquina de Turing determinista.
Referències
Categoria:Classes de complexitat Categoria:Complexitat computacional