У рачунарској теорији сложености, недетерминистички простор NSPACE је рачунарски ресурс који описује меморијски простор за недетерминистичку Тјурингову машину. То је недетерминистички пандан DSPACE-а.

Мера NSPACE се користи за дефинисање класе сложености проблема чија решења могу да буду одређена помоћу недетерминистичке Тјурингове машине. Класа сложености NSPACE(f(n)) је скуп проблема одлучивања који могу да буду решени помоћу недетерминистичке Тјурингове машине M, коришћењем простора O(f(n)), где је f(n) максимални број ћелија траке које M скенира на сваки улаз дужине n.^[1]

Неколико важних класа сложености може да се дефинише у односу на NSPACE. То су:

• REG = DSPACE(O(1)) = NSPACE(O(1)), где је REG класа регуларних језика (недетерминизам не повећава снагу у константном простору).
• NL = NSPACE(O(log n))
• CSL = NSPACE'(O(n)), где је CSL класа контекстно-сензитивних језика.
• PSPACE = NPSPACE = ${\displaystyle \bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}(n^{k})}$
• EXPSPACE = NEXPSPACE = ${\displaystyle \bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}(2^{n^{k}})}$

Теорема Имермана и Селепчењија утврђује да је NSPACE(s(n)) затворена за допуне за сваку функцију s(n) ≥ log n. Даља генерализација је ASPACE, дефинисана за алтернирајућу Тјурингову машину.

DSPACE NSPACE је недетерминистички пар DSPACE-а, класом меморијског простора за детерминистичку Тјурингову машину. Према теореми Севича имамо да је:

${\displaystyle {\mbox{DSPACE}}[s(n)]\subseteq {\mbox{NSPACE}}[s(n)]\subseteq {\mbox{DSPACE}}[(s(n))^{2}].}$

Time

NSPACE може да се користо за одређивање временске сложености детерминистичке Тјурингове машине према следећој теореми:

Ако је језик L одлучен у простору S(n) (где је S(n) ≥ log n) помоћу недетерминистичке Тјурингове машине, онда постоји константа C таква да L може да буде одлучен у времену O(CS(n)) са детерминистичком машином.^[2]

Мера просторне сложености у односу на DSPACE је корисна зато што представља укупну количину меморије која је потребна да би конкретни рачунар решио задати рачунарски проблем са задатим алгоритмом. Разлог је што DSPACE описује просторну сложеност за детерминистичку Тјурингову машину која може да представља стварни рачунар. Са друге стране, NSPACE описује просторну сложеност недетерминистичке Тјурингове машине, која није од користи за стварне рачунаре. Из тог разлога, примена NSPACE у реалном свету је ограничена.