NSPACE

U računarskoj teoriji složenosti, nedeterministički prostor NSPACE je računarski resurs koji opisuje memorijski prostor za nedeterminističku Tjuringovu mašinu. To je nedeterministički pandan DSPACE-a.

Klase složenosti

Mera NSPACE se koristi za definisanje klase složenosti problema čija rešenja mogu da budu određena pomoću nedeterminističke Tjuringove mašine. Klasa složenosti NSPACE(f(n)) je skup problema odlučivanja koji mogu da budu rešeni pomoću nedeterminističke Tjuringove mašine M, korišćenjem prostora O(f(n)), gde je f(n) maksimalni broj ćelija trake koje M skenira na svaki ulaz dužine n.

Nekoliko važnih klasa složenosti može da se definiše u odnosu na NSPACE. To su:

• REG = DSPACE(O(1)) = NSPACE(O(1)), gde je REG klasa regularnih jezika (nedeterminizam ne povećava snagu u konstantnom prostoru).
• NL = NSPACE(O(log n))
• CSL = NSPACE'(O(n)), gde je CSL klasa kontekstno-senzitivnih jezika.
• PSPACE = NPSPACE = $\bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}(n^{k})$
• EXPSPACE = NEXPSPACE = $\bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}(2^{n^{k}})$

Teorema Imermana i Selepčenjija utvrđuje da je NSPACE(s(n)) zatvorena za dopune za svaku funkciju s(n) ≥ log n. Dalja generalizacija je ASPACE, definisana za alternirajuću Tjuringovu mašinu.

Relacije sa drugim klasama složenosti

DSPACE NSPACE je nedeterministički par DSPACE-a, klasom memorijskog prostora za determinističku Tjuringovu mašinu. Prema teoremi Seviča imamo da je:

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

Time

NSPACE može da se koristo za određivanje vremenske složenosti determinističke Tjuringove mašine prema sledećoj teoremi:

Ako je jezik L odlučen u prostoru S(n) (gde je S(n) ≥ log n) pomoću nedeterminističke Tjuringove mašine, onda postoji konstanta C takva da L može da bude odlučen u vremenu O(CS(n)) sa determinističkom mašinom.

Ograničenja

Mera prostorne složenosti u odnosu na DSPACE je korisna zato što predstavlja ukupnu količinu memorije koja je potrebna da bi konkretni računar rešio zadati računarski problem sa zadatim algoritmom. Razlog je što DSPACE opisuje prostornu složenost za determinističku Tjuringovu mašinu koja može da predstavlja stvarni računar. Sa druge strane, NSPACE opisuje prostornu složenost nedeterminističke Tjuringove mašine, koja nije od koristi za stvarne računare. Iz tog razloga, primena NSPACE u realnom svetu je ograničena.

Literatura

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