NSPACE
classe de complexita / From Wikipedia, the free encyclopedia
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.[1][2]
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.