PSPACE

У теорији рачунске комплексности, PSPACE представља скуп свих проблема одлуке који се могу решити од стране Тјурингове машине користећи полиномијалну количину простора. PSPACE представља један од неразјашњених проблема у рачунарским наукама.^[1]

Формална дефиниција уреди

Ако означимо са SPACE(t(n)) скуп свих проблема који се могу решити Тјурингова машина (Апстрактна машина)Тјуринговом машином користећи O(t(n)) простор за неку функцију t улазне величине n, тада можемо дефинисати PSPACE формално као

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

Ово значи да иако дозвољавамо Тјуринговој машини да буде недетерминистичка, то јој не додаје никакав значај. Због Севичеве теореме, NPSPACE је еквивалент PSPACE, посебно јер детерминистичка Тјурингова машина може да симулира недетерминистичку Тјурингову машину без претерано великог додатог простора (иако ће можда захтевати више времена). Такође, комплементи свих проблема у PSPACE су у PSPACE, што значи да је co-PSPACE = PSPACE.

Односи са другим класама уреди

PSPACE подскупови комплексности

Следеће релације су познате између PSPACE и класа комплексности NL, P, NP, PH, EXPTIME и EXPSPACE (обратити пажњу да ⊊ није исто што и ⊈):

\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}

Познато је да у првом и другом реду, бар један од чланова скупа мора бити стриктан, али не зна се који. Сумња се да сви могу бити стриктни. За чланове у трећем реду се зна да су оба стриктна. Први следи из директне дијагонализације (теорема хијерархије простора, NL ⊊ NPSPACE) и чињенице да је PSPACE = NPSPACE из Севичеве теореме. Друга следи једноставно из теореме хијерархије простора. Најтежи проблеми у PSPACE су PSPACE-комплетни проблеми.

Особине затворености уреди

Класа PSPACE је затворена под операцијама уније, комплементације и Клинове звезде.

Друге особине уреди

Алтернативна карактеризација PSPACE је скуп проблема решивих од стране алтернирајуће Тјурингове машине у полиномијалном времену, понекад зван и APTIME или само AP. Логичка карактеризација PSPACE из дескриптивне теорије комплексности је та да је то скуп проблема описивих логиком другом реда, при чему треба водити рачуна и о оператору транзитивне затворености. PSPACE се може окарактерисати као класа квантне комплексности QIP. PSPACE је такође једнак PCTC, проблемима решивим од стране класичних рачунара, као и BQPCTC, проблемима решивим од стране квантних рачунара.

PSPACE потпуност уреди

Језик Б је PSPACE-комплетан ако се налази у PSPACE и ако је тежине PSPACE, што значи да за сва A ∈ PSPACE, A \leq_p B, where A \leq_p B, што значи да постоји редукција у полиномијалном времену из А у Б. PSPACE-комплетни проблеми су од великог значаја за проучавање PSPACE проблема јер они представљају најтеже проблеме у PSPACE. Проналажење једноставног решења за PSPACE-комплетан проблем би значило да имамо једноставно решење за све остале проблеме у PSPACE јер би се сви PSPACE проблеми могли редуковати на PSPACE-комплетни проблем. Пример PSPACE-комплетног проблема је квантификована Булеан формула проблем, углавном скраћиван као QBF или TQBF.

Види још уреди

Референце уреди

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

Спољашње везе уреди

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). стр. 281–294.
Papadimitriou, Christos (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 978-0-201-53082-7. Chapter 19: Polynomial space. стр. 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]