PSPACE-luokka

PSPACE-monimutkaisuusluokka on joukko laskennallisen monimutkaisuusteorian kaikkia ratkaistavuusongelmia , jotka voidaan ratkaista Turingin koneella polynomialvaruusrajoituksella .

Turingin kone polynomialvaruusrajoituksella

Jos tietylle Turingin koneelle on totta, että on olemassa polynomi p ( n ) , joka millä tahansa syötteellä, jonka koko on n , vierailee enintään p ( n ) solussa, niin tällaista konetta kutsutaan Turingin koneeksi, jolla on polynomitilarajoitus .

Voidaan osoittaa, että:

1. Jos Turingin kone, jonka avaruuden polynomi rajoittaa p ( n ) , niin on olemassa vakio c , jolle tämä kone hyväksyy syötteensä pituudeltaan n enintään askeleena. $c^{1+p(n)}$

Tästä seuraa, että kaikki Turingin konekielet, joissa on polynomiavaruusrajoituksia, ovat rekursiivisia .

Luokat PSPACE, NPSPACE

PSPACE - kieliluokka on joukko kieliä , jotka deterministinen Turingin kone sallii polynomisella tilarajoituksella.

NPSPACE- kieliluokka on joukko kieliä , jotka epädeterministinen Turingin kone sallii polynomisella tilarajoituksella.

Seuraavat väitteet pitävät paikkansa PSPACE- ja NPSPACE-kieliluokissa:

1. PSPACE = NPSPACE (tämä tosiasia todistetaan Savitchin lauseella )

2. Tilanneherkät kielet ovat PSPACE:n osajoukko

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

neljä. ${\mbox{NL}}\subsetneq {\mbox{PSPACE}}\subsetneq {\mbox{EXPSPACE}}$

5. Jos kieli kuuluu PSPACE:hen, on olemassa Turingin kone, jolla on polynomitilarajoitus siten, että se pysähtyy askelittain jollekin c : lle ja polynomille p ( n ) . $c^{p(n)}$

Tiedetään, että ainakin yhden lausunnon kolmesta osallisuussymbolista on oltava tiukka (eli sulje pois joukkojen yhtäläisyys, joiden välistä suhdetta se kuvaa), mutta ei tiedetä, mikä niistä. Lisäksi ainakin yhden lausekkeen osajoukon on oltava oma (eli vähintään yhden sisällyttävän merkin on oltava tiukka). Oletuksena on, että kaikki nämä sisällytykset ovat tiukkoja . $\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

PSPACE-täydellinen ongelma on ongelmaKarpintehtävät voidaanpolynomiajassa. ${\mbox{L}}\in {\mbox{PSPACE)),$

Seuraavat tosiasiat tiedetään PSPACE-täydellisestä ongelmasta:

Jos on PSPACE-täydellinen ongelma, niin ${\mbox{L}}$

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

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

Esimerkki PSPACE-täydellisestä ongelmasta: todellisten loogisten kaavojen löytäminen kvantorien kanssa .

Kirjallisuus

John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Johdatus automaatioteoriaan, kieliin ja laskemiseen. - M . : "Williams" , 2002. - 528 s. - ISBN 0-201-44124-1 .

Hopcroft, Motwani, Ullman: "Johdatus automaatioteoriaan, kieliin ja laskemiseen"

Algoritmien monimutkaisuusluokat
Kevyenä pidetty	DLOGTIME AC 0 ACC 0 TC0 [ fi L SL RL NL NC SC CC P P-täydellinen ZPP RP BPP BQP EQP APX
Taitaa olla vaikeaa	U.P. NP NP valmis co-NP co-NP-täydellinen AM M.A. QMA PH ⊕P PP #P #P - IP_ PSPACE PSPACE-täydellinen
Vaikeaksi pidetty	EXPTIME NEXPTIME EXPACE 2-EXPTIME ELEMENTARY R PR RE täytä uudelleen Co-RE Co-RE-complete KAIKKI