PSPACE

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

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

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

$𝐏𝐒𝐏𝐀𝐂𝐄=\bigcup _{k\in \mathbb{N}}𝐒𝐏𝐀𝐂𝐄(n^k).$

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

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

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

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

$𝐍𝐋\subseteq 𝐏\subseteq 𝐍𝐏\subseteq 𝐏𝐇\subseteq 𝐏𝐒𝐏𝐀𝐂𝐄$

$𝐏𝐒𝐏𝐀𝐂𝐄\subseteq 𝐄𝐗𝐏𝐓𝐈𝐌𝐄\subseteq 𝐄𝐗𝐏𝐒𝐏𝐀𝐂𝐄$

$𝐍𝐋⊊𝐏𝐒𝐏𝐀𝐂𝐄⊊𝐄𝐗𝐏𝐒𝐏𝐀𝐂𝐄$

$𝐏⊊𝐄𝐗𝐏𝐓𝐈𝐌𝐄$

Познато је да у првом и другом реду, бар један од чланова скупа мора бити стриктан, али не зна се који. Сумња се да сви могу бити стриктни. За чланове у трећем реду се зна да су оба стриктна. Први следи из директне дијагонализације (теорема хијерархије простора, 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.

Види још

• Неразјашњени проблеми у рачунарским наукама
• П = НП проблем
• Co-NP
• NL (сложеност)
• Експоненцијално време
• Полиномијално време

Спољашње везе

1. Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. Шаблон:ISBN. Section 8.2–8.3 (The Class PSPACE, PSPACE-completeness). стр. 281–294.
2. Papadimitriou, Christos (1993). Computational Complexity (1st ed.). Addison Wesley. Шаблон:ISBN. Chapter 19: Polynomial space. стр. 455–490.
3. Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). Thomson Course Technology. Шаблон:ISBN. Chapter 8: Space Complexity