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]
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 ⊈):
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 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]
Podrobnější informace naleznete v článku PSPACE-complete.
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]
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
