PSPACE-klass

PSPACE-komplexitetsklassen är uppsättningen av alla lösbarhetsproblem inom beräkningskomplexitetsteori som kan lösas av en Turing-maskin med en polynomisk rymdrestriktion.

Turingmaskin med polynom utrymmesbegränsning

Om det är sant för en given Turing-maskin att det finns ett polynom p ( n ) så att den, vid vilken ingång som helst av storlek n , kommer att besöka högst p ( n ) celler, då kallas en sådan maskin för en Turing-maskin med en polynom utrymmesbegränsning .

Det kan visas att:

1. Om en Turing-maskin med rymden polynomiellt avgränsad av p ( n ) , så finns det en konstant c för vilken denna maskin medger sin inmatning av längden n i högst steg. $c^{1+p(n)}$

Det följer att alla Turing-maskinspråk med polynomiska rymdbegränsningar är rekursiva .

Klasser PSPACE, NPSPACE

Språkklassen PSPACE är uppsättningen språk som tillåts av en deterministisk Turing-maskin med en polynomisk rymdbegränsning.

Språkklassen NPSPACE är uppsättningen språk som tillåts av en icke-deterministisk Turing-maskin med en polynomisk rymdrestriktion.

Följande påståenden är sanna för språkklasserna PSPACE och NPSPACE:

1. PSPACE = NPSPACE (detta bevisas av Savitchs teorem )

2. Kontextkänsliga språk är en delmängd av PSPACE

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

fyra. ${\mbox{NL}}\subsetneq {\mbox{PSPACE}}\subsetneq {\mbox{EXPSPACE}}$

5. Om språket tillhör PSPACE, så finns det en Turing-maskin med en polynomisk rymdbegränsning så att den stannar i steg för något c och ett polynom p ( n ) . $c^{p(n)}$

Det är känt att minst en av de tre inkluderingssymbolerna i påståendet måste vara strikt (det vill säga utesluta jämlikheten mellan uppsättningarna, förhållandet mellan vilka det beskriver), men det är inte känt vilken av dem. Dessutom måste minst en delmängd i en sats vara egen (dvs. minst ett inkluderingstecken måste vara strikt). Det finns ett antagande att alla dessa inneslutningar är strikta . $\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

Ett PSPACE-komplett problem är ett problemenligt Karpkanpolynomtid. ${\mbox{L}}\in {\mbox{PSPACE)),$

Följande fakta är kända om problemet med PSPACE-komplett:

Om är ett PSPACE-komplett problem, då ${\mbox{L}}$

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

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

Ett exempel på ett PSPACE-komplett problem: att hitta sanna booleska formler med kvantifierare .

Litteratur

John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Introduktion till automatteori, språk och beräkningar. - M . : "Williams" , 2002. - 528 sid. - ISBN 0-201-44124-1 .

Hopcroft, Motwani, Ullman: "Introduktion till automatteori, språk och beräkningar"

Komplexitetsklasser av algoritmer
Anses som ljus	DLOGTIME AC 0 ACC 0 TC0 [ sv L SL RL NL NC SC CC P P-komplett ZPP RP BPP BQP EQP APX
Ska vara svårt	U.P. NP NP komplett co-NP co-NP-komplett AM M.A. QMA PH ⊕P PP #P #P- IP PSPACE PSPACE-komplett
Anses vara svårt	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY R PR RE RE-complete Co-RE Co-RE-complete ALLA