PSPACE

PSPACE je v teorii složitosti množina všech rozhodovacích problémů, které lze vyřešit Turingovým strojem používajícím polynomiálně omezené množství paměti.^[1][2][3]

Pokud označíme SPACE(t(n)) množinu všech problémů, které lze vyřešit Turingovým strojem používajícím prostor O(t(n)) pro nějakou funkci t vstupní velikosti n, pak můžeme definovat třídu úloh PSPACE formálně takto:^[4]

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

PSPACE je ostrá nadmnožina množiny kontextových jazyků.

Ukazuje se, že povolením, aby Turingův stroj byl nedeterministický se nezíská žádná významná výhoda. Je to díky Savitchově větě,^[5] NPSPACE je ekvivalentní s PSPACE v zásadě proto, že deterministický Turingův stroj může simulovat nedeterministický Turingův stroj, aniž by bylo potřeba mnohem více prostoru (může však potřebovat mnohem více času).^[6] Také komplementy všech problémů v PSPACE jsou také v PSPACE, což znamená, že co-PSPACE = PSPACE.

Je známo, že platí následující relace mezi PSPACE a třídami složitost NL, P, NP, PH, EXPTIME a EXPSPACE (symbol ⊊, znamenající ostrou inkluzi, není totéž jako ⊈):

${\displaystyle {\begin{array}{l}{\mathsf {NL\subseteq P\subseteq NP\subseteq PH\subseteq PSPACE}}\\{\mathsf {PSPACE\subseteq EXPTIME\subseteq EXPSPACE}}\\{\mathsf {NL\subsetneq PSPACE\subsetneq EXPSPACE}}\\{\mathsf {P\subsetneq EXPTIME}}\end{array}}}$

Z třetího řádku plyne, že v prvním i ve druhém řádku musí být alespoň jedna množinová inkluze ostrá, ale není známo která. Obecně se předpokládá, že jsou ostré všechny.

O inkluzích ve třetím řádku se ví, že jsou ostré. První vyplývá z přímé diagonalizace (věta o hierarchii prostorové složitosti, NL ⊊ NPSPACE) a faktu, že PSPACE = NPSPACE díky Savitchově větě. Druhá plyne jednoduše z věty o hierarchii prostorové složitosti.

Nejtěžší problémy v PSPACE jsou PSPACE-úplné problémy. V článku PSPACE-úplnost jsou uvedeny příklady problémů, o kterých se předpokládá, že jsou v PSPACE ale nejsou v NP.

Třída PSPACE je uzavřená vůči operaci sjednocení, množinového doplňku a Kleeneho hvězdičky.

Alternativní charakterizací PSPACE je množina problémů rozhodnutelných alternujícím Turingovým strojem v polynomiálním čase, někdy nazývaný APTIME nebo pouze AP.^[7]

Logická charakterizace PSPACE z teorie deskriptivní složitosti je, že je to množina problémů vyjadřitelných v logice druhého řádu s přidáným operátorem tranzitivního uzávěru. Není potřeba plný tranzitivní uzávěr; postačuje komutativní tranzitivní uzávěr nebo dokonce slabší formy. Právě přidání tohoto operátoru (případně) rozlišuje PSPACE z PH.

Hlavním výsledkem teorie složitost je, že PSPACE lze charakterizovat jako všechny jazyky rozpoznávané určitým interaktivním dokazovacím systémem, tím, který definuje třídu IP. V tomto systému existuje dokazovací stroj všechno-výkonný, který přesvědčuje pravděpodobnostní verifikátor pracující v polynomiálním čase, že řetězec je v jazyce. Měl by být schopen s vysokou pravděpodobností přesvědčit verififikátor, že řetězec je v jazyce, ale neměl by být schopen jej přesvědčit (až na nízkou pravděpodobnost), že řetězec v jazyce není.

PSPACE lze charakterizovat jako kvantovou třídu složitosti QIP.^[8]

PSPACE je také rovno P_CTC, problémů řešitelných klasickými počítači používajícím uzavřených časupodobných křivek,^[9] i BQP_CTC, problémů řešitelných kvantovými počítači používajícím uzavřených časupodobných křivek.^[10]

Jazyk B je PSPACE-úplný, pokud je v PSPACE a je PSPACE-těžký, což znamená, že pro všechno A ∈ PSPACE, ${\displaystyle A\leq _{\text{P}}B}$, kde ${\displaystyle A\leq _{\text{P}}B}$ znamená, že existuje redukce z mnoha na jeden v polynomiálním čase z A do B. PSPACE-úplné problémy mají velký význam pro studium PSPACE problémů, protože reprezentují nejobtížnější problémy v PSPACE. Naleznutí jednoduchého řešení nějakého PSPACE-úplného problému by znamenalo, že máme jednoduché řešení všech ostatních problémů v PSPACE, protože všechny PSPACE problémy lze redukovat na PSPACE-úplný problém.^[11]

Příkladem PSPACE-úplného problému je problém kvantifikovaného Booleovského vzorce (obvykle zkráceně na QBF nebo TQBF; T znamená „pravdivý“).^[11]

V tomto článku byl použit překlad textu z článku PSPACE na anglické Wikipedii.

• ARORA, Sanjeev; BARAK, Boaz, 2009. Computational complexity. A modern approach. [s.l.]: Cambridge University Press. ISBN 978-0-521-42426-4. 
• SIPSER, Michael, 1997. Introduction to the Theory of Computation. [s.l.]: PWS Publishing. Dostupné online. ISBN 0-534-94728-X. 
• PAPADIMITRIOU, Christos, 1993. Computational Complexity. 1. vyd. [s.l.]: Addison Wesley. ISBN 0-201-53082-1. 
• SIPSER, Michael, 2006. Introduction to the Theory of Computation. 2. vyd. [s.l.]: Thomson Course Technology. ISBN 0-534-95097-3. 
• Rahul Jain; Zhengfeng Ji; Sarvagya Upadhyay; John Watrous, 2009. QIP = PSPACE [online]. Červenec 2009. Dostupné online. 
• AARONSON, S., 2005. NP-complete problems and physical reality. SIGACT News. Březen 2005. DOI 10.1145/1052796.1052804. S2CID 18759797. Bibcode 2005quant.ph..2072A. arXiv quant-ph/0502072. 
• WATROUS, John; AARONSON, Scott, 2009. Closed timelike curves make quantum and classical computing equivalent. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. Roč. 465, čís. 2102, s. 631. DOI 10.1098/rspa.2008.0350. S2CID 745646. Bibcode 2009RSPSA.465..631A. arXiv 0808.2669. 

• Complexity Zoo: P-SPACE