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.Šablona:SfnŠablona:SfnŠablona:Sfn

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:Šablona:Sfn

$𝖯𝖲𝖯𝖠𝖢𝖤=\bigcup _{k\in \mathbb{N}}𝖲𝖯𝖠𝖢𝖤(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ě,Šablona:Sfn 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).Šablona:Sfn Také komplementy všech problémů v PSPACE jsou také v PSPACE, což znamená, že co-PSPACE = PSPACE.

Relace mezi jinými třídami

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 ⊈):

$\begin{array}{c}𝖭𝖫\mathsf{\subseteq }𝖯\mathsf{\subseteq }𝖭𝖯\mathsf{\subseteq }𝖯𝖧\mathsf{\subseteq }𝖯𝖲𝖯𝖠𝖢𝖤\\ 𝖯𝖲𝖯𝖠𝖢𝖤\mathsf{\subseteq }𝖤𝖷𝖯𝖳𝖨𝖬𝖤\mathsf{\subseteq }𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤\\ 𝖭𝖫\mathsf{⊊}𝖯𝖲𝖯𝖠𝖢𝖤\mathsf{⊊}𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤\\ 𝖯\mathsf{⊊}𝖤𝖷𝖯𝖳𝖨𝖬𝖤\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.

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.Šablona:Sfn

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.Šablona:Sfn

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,Šablona:Sfn i BQP_CTC, problémů řešitelných kvantovými počítači používajícím uzavřených časupodobných křivek.Šablona:Sfn

PSPACE-úplnost

Šablona:Podrobně Jazyk B je PSPACE-úplný, pokud je v PSPACE a je PSPACE-těžký, což znamená, že pro všechno A ∈ PSPACE, $A{\le }_{\text{P}}B$, kde $A{\le }_{\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.Šablona:Sfn

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ý“).Šablona:Sfn

Odkazy

Literatura

• Šablona:Citace monografie
• Šablona:Citace monografie
• Šablona:Citace monografie
• Šablona:Citace monografie
• Šablona:Citace elektronické monografie
• Šablona:Citace periodika
• Šablona:Citace periodika

Externí odkazy

• Complexity Zoo: P-SPACE