PSPACE osztály

A PSPACE komplexitási osztály a számítási komplexitáselméletben az összes olyan megoldhatósági probléma halmaza, amely polinomiális térkényszerrel megoldható Turing-géppel .

Turing-gép polinomiális térkényszerrel

Ha egy adott Turing-gépre igaz , hogy létezik olyan p ( n ) polinom , amely bármely n méretű bemeneten legfeljebb p ( n ) cellát látogat meg , akkor egy ilyen gépet Turing-gépnek nevezünk . polinom térkényszer .

Kimutatható, hogy:

1. Ha egy Turing-gép, amelynek térpolinomiálisan p ( n ) határolja , akkor létezik olyan c konstans , amelyre ez a gép legfeljebb lépésben elfogadja az n hosszúságú bemenetét. $c^{1+p(n)}$

Ebből következik, hogy minden polinomiális térmegszorítással rendelkező Turing-gépnyelv rekurzív .

Osztályok PSPACE, NPSPACE

A PSPACE nyelvosztály azon nyelvek halmaza, amelyeket egy determinisztikus Turing-gép engedélyez polinomiális térkényszerrel.

Az NPSPACE nyelvosztály azon nyelvek halmaza, amelyeket egy nemdeterminisztikus Turing -gép polinomiális térkényszerrel engedélyez.

A következő állítások igazak a PSPACE és NPSPACE nyelvosztályokra:

1. PSPACE = NPSPACE (ezt a tényt Savitch tétele bizonyítja )

2. A környezetérzékeny nyelvek a PSPACE egy részhalmazát képezik

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

négy. ${\mbox{NL}}\subsetneq {\mbox{PSPACE}}\subsetneq {\mbox{EXPSPACE}}$

5. Ha a nyelv a PSPACE-hoz tartozik, akkor van egy Turing-gép, amelynek polinomiális térkényszere van úgy, hogy néhány c és egy p ( n ) polinom esetén lépésenként megáll . $c^{p(n)}$

Ismeretes, hogy az állításban szereplő három befogadó szimbólum közül legalább egynek szigorúnak kell lennie (azaz kizárja a halmazok egyenlőségét, a köztük lévő kapcsolatot), de nem tudni, hogy melyikük. Ezenkívül az utasításban legalább egy részhalmaznak sajátnak kell lennie (azaz legalább egy szerepeltetési karakternek szigorúnak kell lennie). Feltételezhető, hogy ezek a zárványok szigorúak . $\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

A PSPACE-teljes probléma olyan problémaKarp szerintredukálhatópolinomiális időben. ${\mbox{L}}\in {\mbox{PSPACE)),$

A következő tények ismertek a PSPACE-teljes problémáról:

Ha PSPACE-teljes probléma, akkor ${\mbox{L}}$

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

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

Példa egy PSPACE-teljes problémára: valódi logikai képletek keresése kvantorokkal .

Irodalom

John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Bevezetés az automataelméletbe, a nyelvekbe és a számításba. - M . : "Williams" , 2002. - 528 p. - ISBN 0-201-44124-1 .

Hopcroft, Motwani, Ullman: "Bevezetés az automataelméletbe, a nyelvekbe és a számításba"

Algoritmusok összetettségi osztályai
Fénynek tekinthető	DLOGTIME AC 0 ACC 0 TC0 [ hu L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP EQP APX
Állítólag nehéz	U.P. NP NP kész co-NP társNP-teljes AM M.A. QMA PH ⊕P PP #P #P- IP_ PSPACE PSPACE-teljes
Nehéznek tartott	LEJÁRATI IDŐ NEXPTIME KIFEJEZÉS 2-EXPTIME ELEMENTARY R PR RE töltse ki újra Co-RE Co-RE-complete ÖSSZES