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]
Formální definice editovat
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]
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.
Relace mezi jinými třídami editovat
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 ⊈):
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.
Uzávěrové vlastnosti editovat
Třída PSPACE je uzavřená vůči operaci sjednocení, množinového doplňku a Kleeneho hvězdičky.
Jiné charakterizace editovat
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 PCTC, problémů řešitelných klasickými počítači používajícím uzavřených časupodobných křivek,[9] i BQPCTC, problémů řešitelných kvantovými počítači používajícím uzavřených časupodobných křivek.[10]
PSPACE-úplnost editovat
Jazyk B je PSPACE-úplný, pokud je v PSPACE a je PSPACE-těžký, což znamená, že pro všechno A ∈ PSPACE, , kde 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]
Odkazy editovat
Poznámky editovat
- ↑ Sipser 1997, Section 8.2–8.3 (The Class PSPACE, PSPACE-completeness), pp. 281–294.
- ↑ Sipser 2006, Chapter 8: Space Complexity.
- ↑ Papadimitriou 1993, Chapter 19: Polynomial space, pp. 455–490.
- ↑ Arora a Barak 2009, s. 81.
- ↑ Arora a Barak 2009, s. 85.
- ↑ Arora a Barak 2009, s. 86.
- ↑ Arora a Barak 2009, s. 100.
- ↑ QIP-PSPACE.
- ↑ Aaronson 2005.
- ↑ Watrous a Aaronson 2009.
- ↑ a b Arora a Barak 2009, s. 83.
Reference editovat
V tomto článku byl použit překlad textu z článku PSPACE na anglické Wikipedii.
Literatura editovat
- 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.