Изворни код странице NSPACE


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

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

Мера ''NSPACE'' се користи за дефинисање [[Класа сложености|класе сложености]] проблема чија решења могу да буду одређена помоћу недетерминистичке Тјурингове машине. Класа сложености ''NSPACE(f(n))'' је скуп [[Проблем одлучивања|проблема одлучивања]] који могу да буду решени помоћу [[Недетерминистичка Тјурингова машина|недетерминистичке Тјурингове машине]] M, коришћењем простора '''O(f(n))''', где је ''f(n)'' максимални број ћелија траке које M скенира на сваки улаз дужине n.<ref>{{harvnb|Sipser|2006|pp=303–304}}</ref>

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

* ''REG'' = ''DSPACE(O(1))'' = ''NSPACE(O(1))'', где је REG класа [[Regularni jezik|регуларних језика]] (недетерминизам не повећава снагу у константном простору).
* ''NL'' = NSPACE(O(log n))
* ''CSL'' = ''NSPACE''''(O(n))'', где је ''CSL'' класа контекстно-сензитивних језика.
* ''PSPACE'' = ''NPSPACE'' = <math>\bigcup_{k\in\mathbb{N}} \mbox{NSPACE}(n^k)</math>
* ''EXPSPACE'' = ''NEXPSPACE'' = <math>\bigcup_{k\in\mathbb{N}} \mbox{NSPACE}(2^{n^k})</math>

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

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

'''DSPACE'''
''NSPACE'' је недетерминистички пар DSPACE-а, класом меморијског простора за детерминистичку Тјурингову машину. Према теореми Севича имамо да је:
<blockquote>
<math>\mbox{DSPACE}[s(n)] \subseteq \mbox{NSPACE}[s(n)] \subseteq \mbox{DSPACE}[(s(n))^2].</math>
</blockquote>
 
'''Time'''

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

Ако је језик ''L'' одлучен у простору ''S(n)'' (где је ''S(n) ≥ log n'') помоћу недетерминистичке Тјурингове машине, онда постоји константа ''C'' таква да ''L'' може да буде одлучен у времену ''O(CS(n))'' са детерминистичком машином.{{sfn|Goddard|2008|p=183}}


== Ограничења ==

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

== Референце ==
{{reflist|30em}}

== Литература ==
* {{Cite book |ref= harv|last=Goddard|first=Wayne|title=Introducing the Theory of Computation|year=2008|publisher=Jones and Bartlett Publishers, Inc.|isbn=978-0-7637-4125-9|pages=183}}
* {{Cite book |ref= harv|last=Sipser|first=Michael|title=Introduction to the Theory of Computation (2nd ed.)|year=2006|publisher=Course Technology|isbn=978-0-534-95097-2|pages=303–304}}

{{нормативна контрола}}

[[Категорија:Класе комплексности]]