PSPACE klasse

PSPACE-kompleksitetsklassen er sættet af alle løselighedsproblemer i beregningskompleksitetsteori, der kan løses af en Turing-maskine med en polynomisk rumbegrænsning.

Turing-maskine med polynomisk rumbegrænsning

Hvis det er sandt for en given Turing-maskine , at der eksisterer et polynomium p ( n ), således at det ved enhver input af størrelse n højst vil besøge p ( n ) celler, så kaldes en sådan maskine en Turing-maskine med en polynomisk rumbegrænsning .

Det kan vises, at:

1. Hvis en Turing-maskine med rumpolynomium afgrænset af p ( n ) , så eksisterer der en konstant c , for hvilken denne maskine tillader sit input af længden n i ikke mere end trin. $c^{1+p(n)}$

Det følger heraf, at alle Turing-maskinesprog med polynomiske rumbegrænsninger er rekursive .

Klasser PSPACE, NPSPACE

PSPACE - sprogklassen er det sæt af sprog, der er tilladt af en deterministisk Turing-maskine med en polynomisk rumbegrænsning.

NPSPACE- sprogklassen er det sæt af sprog, der er tilladt af en ikke-deterministisk Turing-maskine med en polynomisk rumbegrænsning.

Følgende udsagn er sande for sprogklasserne PSPACE og NPSPACE:

1. PSPACE = NPSPACE (dette faktum er bevist af Savitchs sætning )

2. Kontekstfølsomme sprog er en delmængde af PSPACE

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

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

5. Hvis sproget hører til PSPACE, så er der en Turing-maskine med en polynomisk rumbegrænsning, så den stopper i trin for nogle c og et polynomium p ( n ) . $c^{p(n)}$

Det er kendt, at mindst et af de tre inklusionssymboler i udsagnet skal være strengt (det vil sige udelukke ligheden af sættene, det forhold, som det beskriver), men det vides ikke, hvilket af dem. Desuden skal mindst ét undersæt i en sætning være eget (dvs. mindst ét inklusionstegn skal være strengt). Der er en antagelse om, at alle disse indeslutninger er strenge . $\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

Et PSPACE-komplet problem er et problemifølge Karpkanpolynomisk tid. ${\mbox{L}}\in {\mbox{PSPACE)),$

Følgende fakta er kendt om PSPACE-komplet-problemet:

Hvis er et PSPACE-komplet problem, så ${\mbox{L}}$

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

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

Et eksempel på et PSPACE-komplet problem: at finde ægte booleske formler med kvantifikatorer .

Litteratur

John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Introduktion til automatteori, sprog og beregning. - M . : "Williams" , 2002. - 528 s. - ISBN 0-201-44124-1 .

Hopcroft, Motwani, Ullman: "Introduktion til automatteori, sprog og beregninger"

Kompleksitetsklasser af algoritmer
Betragtes som lys	DLOGTIME AC 0 ACC 0 TC0 [ da L SL RL NL NC SC CC P P-komplet ZPP RP BPP BQP EQP APX
Formodes at være svært	U.P. NP NP komplet co-NP co-NP-komplet AM M.A. QMA PH ⊕P PP #P #P- IP PSPACE PSPACE-komplet
Anses for vanskelig	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY R PR RE RE-complete Co-RE Co-RE-complete ALLE