PSPACE

U teoriji računske kompleksnosti, PSPACE predstavlja skup svih problema odluke koji se mogu rešiti od strane Tjuringove mašine koristeći polinomijalnu količinu prostora. PSPACE predstavlja jedan od nerazjašnjenih problema u računarskim naukama.^[1]

Formalna definicija uredi

Ako označimo sa SPACE(t(n)) skup svih problema koji se mogu rešiti Tjuringova mašina (Apstraktna mašina)Tjuringovom mašinom koristeći O(t(n)) prostor za neku funkciju t ulazne veličine n, tada možemo definisati PSPACE formalno kao

\mathbf {PSPACE} =\bigcup _{k\in \mathbb {N} }\mathbf {SPACE} (n^{k}).

Ovo znači da iako dozvoljavamo Tjuringovoj mašini da bude nedeterministička, to joj ne dodaje nikakav značaj. Zbog Sevičeve teoreme, NPSPACE je ekvivalent PSPACE, posebno jer deterministička Tjuringova mašina može da simulira nedeterminističku Tjuringovu mašinu bez preterano velikog dodatog prostora (iako će možda zahtevati više vremena). Takođe, komplementi svih problema u PSPACE su u PSPACE, što znači da je co-PSPACE = PSPACE.

Odnosi sa drugim klasama uredi

PSPACE podskupovi kompleksnosti

Sledeće relacije su poznate između PSPACE i klasa kompleksnosti NL, P, NP, PH, EXPTIME i EXPSPACE (obratiti pažnju da ⊊ nije isto što i ⊈):

\mathbf {NL} \subseteq \mathbf {P} \subseteq \mathbf {NP} \subseteq \mathbf {PH} \subseteq \mathbf {PSPACE}

\mathbf {PSPACE} \subseteq \mathbf {EXPTIME} \subseteq \mathbf {EXPSPACE}

\mathbf {NL} \subsetneq \mathbf {PSPACE} \subsetneq \mathbf {EXPSPACE}

\mathbf {P} \subsetneq \mathbf {EXPTIME}

Poznato je da u prvom i drugom redu, bar jedan od članova skupa mora biti striktan, ali ne zna se koji. Sumnja se da svi mogu biti striktni. Za članove u trećem redu se zna da su oba striktna. Prvi sledi iz direktne dijagonalizacije (teorema hijerarhije prostora, NL ⊊ NPSPACE) i činjenice da je PSPACE = NPSPACE iz Sevičeve teoreme. Druga sledi jednostavno iz teoreme hijerarhije prostora. Najteži problemi u PSPACE su PSPACE-kompletni problemi.

Osobine zatvorenosti uredi

Klasa PSPACE je zatvorena pod operacijama unije, komplementacije i Klinove zvezde.

Druge osobine uredi

Alternativna karakterizacija PSPACE je skup problema rešivih od strane alternirajuće Tjuringove mašine u polinomijalnom vremenu, ponekad zvan i APTIME ili samo AP. Logička karakterizacija PSPACE iz deskriptivne teorije kompleksnosti je ta da je to skup problema opisivih logikom drugom reda, pri čemu treba voditi računa i o operatoru tranzitivne zatvorenosti. PSPACE se može okarakterisati kao klasa kvantne kompleksnosti QIP. PSPACE je takođe jednak PCTC, problemima rešivim od strane klasičnih računara, kao i BQPCTC, problemima rešivim od strane kvantnih računara.

PSPACE potpunost uredi

Jezik B je PSPACE-kompletan ako se nalazi u PSPACE i ako je težine PSPACE, što znači da za sva A ∈ PSPACE, A \leq_p B, where A \leq_p B, što znači da postoji redukcija u polinomijalnom vremenu iz A u B. PSPACE-kompletni problemi su od velikog značaja za proučavanje PSPACE problema jer oni predstavljaju najteže probleme u PSPACE. Pronalaženje jednostavnog rešenja za PSPACE-kompletan problem bi značilo da imamo jednostavno rešenje za sve ostale probleme u PSPACE jer bi se svi PSPACE problemi mogli redukovati na PSPACE-kompletni problem. Primer PSPACE-kompletnog problema je kvantifikovana Bulean formula problem, uglavnom skraćivan kao QBF ili TQBF.

Vidi još uredi

Reference uredi

^ Arora, Sanjeev; Barak, Boaz . Computational complexity. A modern approach. Cambridge University Press. 2009. ISBN 978-0-521-42426-4.. Zbl 1193.68112.

Spoljašnje veze uredi

Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 978-0-534-94728-6. Section 8.2–8.3 (The Class PSPACE, PSPACE-completeness). str. 281–294.
Papadimitriou, Christos (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 978-0-201-53082-7. Chapter 19: Polynomial space. str. 455–490.
Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). Thomson Course Technology. ISBN 978-0-534-95097-2. Chapter 8: Space Complexity

[1] Arora, Sanjeev; Barak, Boaz . Computational complexity. A modern approach. Cambridge University Press. 2009. ISBN 978-0-521-42426-4.. Zbl 1193.68112.

[1]