Třída PSPACE

Třída složitosti PSPACE je soubor všech problémů řešitelnosti v teorii výpočetní složitosti , které lze vyřešit Turingovým strojem s polynomiálním prostorovým omezením.

Turingův stroj s polynomiálním prostorovým omezením

Pokud pro daný Turingův stroj platí , že existuje polynom p ( n ) takový, že na libovolném vstupu o velikosti n navštíví nejvýše p ( n ) buněk, pak se takový stroj nazývá Turingův stroj s polynomiální prostorové omezení .

Lze ukázat, že:

1. Jestliže Turingův stroj s prostorem polynomiálně ohraničeným p ( n ) , pak existuje konstanta c , pro kterou tento stroj připouští svůj vstup délky n v maximálně krocích. $c^{1+p(n)}$

Z toho vyplývá, že všechny jazyky Turingových strojů s polynomiálními prostorovými omezeními jsou rekurzivní .

Třídy PSPACE, NPSPACE

Jazyková třída PSPACE je sada jazyků povolených deterministickým Turingovým strojem s polynomiálním prostorovým omezením.

Jazyková třída NPSPACE je sada jazyků povolených nedeterministickým Turingovým strojem s polynomiálním prostorovým omezením.

Následující tvrzení platí pro jazykové třídy PSPACE a NPSPACE:

1. PSPACE = NPSPACE (tuto skutečnost dokazuje Savitchova věta )

2. Kontextově citlivé jazyky jsou podmnožinou PSPACE

3. ${\mbox{NL}}\subseteq {\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{PSPACE}}\subseteq {\mbox{EXPTIME}}$

čtyři. ${\mbox{NL}}\subsetneq {\mbox{PSPACE}}\subsetneq {\mbox{EXPSPACE}}$

5. Pokud jazyk patří do PSPACE, pak existuje Turingův stroj s polynomiálním prostorovým omezením takovým, že se zastaví v krocích pro nějaké c a polynom p ( n ) . $c^{p(n)}$

Je známo, že alespoň jeden ze tří inkluzních symbolů ve výroku musí být striktní (tedy vyloučit rovnost množin, vztah mezi nimiž popisuje), ale není známo, který z nich. Alespoň jedna podmnožina v příkazu musí být také vlastní (tj. alespoň jeden vkládací znak musí být striktní). Existuje předpoklad, že všechny tyto inkluze jsou striktní . $\subseteq$ ${\mbox{NL}}\subseteq {\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{PSPACE}}$ $(\subsetneq )$ ${\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{PSPACE}}\subseteq {\mbox{EXPTIME}}$ $(\subsetneq )$

PSPACE-Complete Challenge

Úplný problém PSPACE je problémlzepodle Karpapolynomiálním čase. ${\mbox{L}}\v {\mbox{PSPACE)),$

O problému PSPACE-complete jsou známy následující skutečnosti:

Pokud je to problém s PSPACE, pak ${\mbox{L}}$

jeden. ${\mbox{L}}\in {\mbox{P}}\Rightarrow {\mbox{P}}={\mbox{PSPACE}};$

2. ${\mbox{L}}\in {\mbox{NP}}\Rightarrow {\mbox{NP}}={\mbox{PSPACE}}.$

Příklad problému úplného PSPACE: hledání pravdivých booleovských vzorců s kvantifikátory .

Literatura

John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Úvod do teorie automatů, jazyků a počítání. - M .: "Williams" , 2002. - 528 s. - ISBN 0-201-44124-1 .

Hopcroft, Motwani, Ullman: „Úvod do teorie automatů, jazyků a počítání“

Třídy složitosti algoritmů
Považováno za světlo	DLOGTIME AC 0 ACC 0 TC0 [ en L SL RL NL NC SC CC P P-kompletní ZPP RP BPP BQP EQP APX
Prý to bude těžké	U.P. NP NP kompletní co-NP co-NP-kompletní AM M.A. QMA PH ⊕P PP #P #P- IP PSPACE PSPACE-complete
Považováno za obtížné	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY R PR RE RE-complete Co-RE Co-RE-complete VŠECHNY