Polynomhierarki

I komplexitetsteorin är en polynomhierarki en hierarki av komplexitetsklasser som generaliserar klasserna P, NP, co-NP till orakelberäkningar .

Definition

Det finns många likvärdiga definitioner av polynomhierarkiklasserna. Låt oss ta en av dem.

För att definiera ett orakel i en polynomhierarki definierar vi

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

där P är mängden problem som ska lösas i polynomtid. Sedan definierar vi för 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}} }}}}

Där A B är den uppsättning problem som löses av en Turing-maskin i klass A utökad med ett orakel för något problem från klass B. Till exempel, , och är en klass av problem lösta i polynomtid med ett orakel för något problem från NP . $\Sigma _{1}^{{{\rm {P}}}}={{\rm {NP}}}},\Pi _{1}^{({\rm {P}}}}={ { \rm {coNP}}}$ $\Delta _{2}^{{{\rm {P))))={{\rm {P^{{NP))))}$

Relationer mellan klasser i en polynomhierarki

Definitionerna innebär följande samband:

\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}}}}

Till skillnad från de aritmetiska och analytiska hierarkierna, där alla inneslutningar är strikta, är frågan om strikthet fortfarande öppen i polynomhierarkin.

Om någon , eller någon , krymper hierarkin ner till nivå k : för alla , . I praktiken betyder detta att likheten mellan klasserna P och NP fullständigt förstör polynomhierarkin. $\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)))))$

Unionen av alla klasser i polynomhierarkin är klassen PH .

Polynomhierarkin är motsvarigheten (med mindre komplexitet) till den aritmetiska hierarkin.

Det är känt att PH finns i PSPACE , men det är inte känt om de två klasserna är lika.

En användbar omformulering av det senaste problemet: PH = PSPACE om och endast om andra ordningens logik inte får extra kardinalitet genom att lägga till en transitiv stängningsoperator .

Varje klass i polynomhierarkin innehåller -kompletta problem (problemen är kompletta med avseende på Karp-reduktion i polynomtid). $\leq _{({\rm {m))))^{({\rm {P))))$