NSPACE

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

Класе сложености

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

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

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

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

Релације са другим класама сложености

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

${\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)) са детерминистичком машином.

Ограничења

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

Литература

• Goddard, Wayne (2008). Introducing the Theory of Computation. Jones and Bartlett Publishers, Inc. стр. 183. ISBN 978-0-7637-4125-9. 
• Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). Course Technology. стр. 303—304. ISBN 978-0-534-95097-2.