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.
Formální definice 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:
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ě, 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). Také komplementy všech problémů v PSPACE jsou také v PSPACE, což znamená, že co-PSPACE PSPACE.
Relace mezi jinými třídami 300px|náhled|vpravo|Reprezentace relací mezi třídami složitosti 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 Třída PSPACE je uzavřená vůči operaci sjednocení, množinového doplňku a Kleeneho hvězdičky.
Jiné charakterizace 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.
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.
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, i BQPCTC, problémů řešitelných kvantovými počítači používajícím uzavřených časupodobných křivek.
PSPACE-úplnost
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.
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ý“).
Odkazy
Poznámky
Reference
Literatura
Externí odkazy Complexity Zoo: P-SPACE
Kategorie:Třídy složitosti