Polynomisk hierarki

I kompleksitetsteori er et polynomiumhierarki et hierarki af kompleksitetsklasser, der generaliserer klasserne P, NP, co-NP til orakelberegninger .

Definition

Der er mange ækvivalente definitioner af polynomielle hierarkiklasser. Lad os tage en af dem.

For at definere et orakel i et polynomiumhierarki, definerer vi

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

hvor P er mængden af problemer, der skal løses i polynomisk tid. Så definerer vi for 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}} }}}}

Hvor A B er det sæt af problemer, der løses af en Turing-maskine i klasse A, udvidet med et orakel for et eller andet problem fra klasse B. For eksempel, , og er en klasse af problemer løst i polynomisk tid med et orakel for et eller andet problem fra NP . $\Sigma _{1}^{{{\rm {P}}}}={{\rm {NP}}}},\Pi _{1}^{({\rm {P}}}}={ { \rm {coNP}}}$ $\Delta _{2}^{{{\rm {P))))={{\rm {P^{{NP))))}$

Relationer mellem klasser i et polynomiumhierarki

Definitionerne antyder følgende forhold:

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

I modsætning til de aritmetiske og analytiske hierarkier, hvor alle inklusioner er strenge, er spørgsmålet om strenghed stadig åbent i polynomiehierarkiet.

Hvis nogen , eller nogen , så krymper hierarkiet ned til niveau k : for alle , . I praksis betyder det, at ligheden af klasserne P og NP fuldstændig ødelægger polynomiehierarkiet. $\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)))))$

Foreningen af alle klasser i polynomiumhierarkiet er klassen PH .

Det polynomielle hierarki er modstykket (med mindre kompleksitet) til det aritmetiske hierarki.

Det er kendt, at PH er indeholdt i PSPACE , men det vides ikke, om de to klasser er ens.

En nyttig genformulering af det sidste problem: PH = PSPACE hvis og kun hvis andenordens logik ikke får ekstra kardinalitet ved at tilføje en transitiv lukningsoperator .

Hver klasse i polynomiehierarkiet indeholder -komplet-problemer (problemerne er komplette med hensyn til Karp-reduktion i polynomietid). $\leq _{({\rm {m))))^{({\rm {P))))$