Polynomihierarkia

Monimutkaisuusteoriassa polynomihierarkia on monimutkaisuusluokkien hierarkia, joka yleistää luokat P, NP, co-NP oraakkelilaskelmille .

Määritelmä

Polynomihierarkialuokille on monia vastaavia määritelmiä. Otetaan yksi niistä.

Määrittelemme oraakkelin polynomihierarkiassa

\Delta _{0}^{{\rm {P)))):=\Sigma _{0}^{{{\rm {P)))):=\Pi _{0}^{{{ \rm {P)))):={\mbox{P}},

jossa P on joukko polynomiajassa ratkaistavia tehtäviä. Sitten määritämme arvolle i ≥ 0

\Delta _{{i+1}}^{{{\rm {P}}}}:={\mbox{P}}^{{\Sigma _{i}^{{{\rm {P}} }}}}

\Sigma _{{i+1}}^{{{\rm {P}}}}:={\mbox{NP}}^{{\Sigma _{i}^{{{\rm {P}} }}}}

\Pi _{{i+1}}^{{{\rm {P}}}}:={\mbox{coNP}}^({\Sigma _{i}^{{{\rm {P}} }}}}

Missä A B on luokan A Turingin koneen ratkaisemien tehtävien joukko, joka on laajennettu jonkin luokan B tehtävän oraakkelilla . Esimerkiksi , ja on luokka tehtäviä, jotka ratkaistaan polynomiajassa oraakkelilla jollekin tehtävälle NP :stä . $\Sigma _{1}^{{{\rm {P}}}}={{\rm {NP}}}},\Pi _{1}^{({\rm {P}}}}={ { \rm {conP}}}$ $\Delta _{2}^{{{\rm {P))))={{\rm {P^{{NP))))}$

Luokkien väliset suhteet polynomihierarkiassa

Määritelmät tarkoittavat seuraavia suhteita:

\Sigma _{i}^{{{\rm {P))))\subseteq \Delta _{{i+1}}^{{{\rm {P))))\subseteq \Sigma _{{i +1))^{{{\rm {P))))

\Pi _{i}^{({\rm {P))))\subseteq \Delta _{{i+1}}^{({\rm {P))))\subseteq \Pi _{{i +1))^{{{\rm {P))))

\Sigma _{i}^{{{\rm {P}}}}={{\rm {co}}}\Pi _{{i}}^{{{\rm {P}}}}

Toisin kuin aritmeettinen ja analyyttinen hierarkia, jossa kaikki inkluusiot ovat tiukkoja, polynomihierarkiassa tiukkuuden kysymys on edelleen avoin.

Jos jokin tai mikä tahansa , hierarkia kutistuu tasolle k : kaikille , . Käytännössä tämä tarkoittaa, että luokkien P ja NP yhtäläisyys tuhoaa polynomihierarkian kokonaan. $\Sigma _{k}^{{{\rm {P))))=\Sigma _{{k+1}}^{({\rm {P))))$ $\Sigma _{k}^{{{\rm {P}}}}=\Pi _{{k}}^{{{\rm {P}}}}$ $i>k$ $\Sigma _{i}^{{{\rm {P))))=\Sigma _{k}^{({\rm {P))))$

Polynomihierarkian kaikkien luokkien liitto on luokka PH .

Polynomihierarkia on (vähemmän monimutkaisempi) aritmeettisen hierarkian vastine.

Tiedetään, että PH sisältyy PSPACE :hen , mutta ei tiedetä, ovatko nämä kaksi luokkaa samanarvoisia.

Hyödyllinen uusinta viimeisestä tehtävästä: PH = PSPACE , jos ja vain jos toisen kertaluvun logiikka ei saa ylimääräistä kardinaalisuutta lisäämällä transitiivista sulkemisoperaattoria .

Jokainen polynomihierarkian luokka sisältää -täydelliset tehtävät (ongelmat ovat täydellisiä suhteessa Karp-pelkistykseen polynomiajassa). $\leq _{({\rm {m))))^{({\rm {P))))$