Ierarhia polinomială

În teoria complexității, o ierarhie polinomială este o ierarhie a claselor de complexitate care generalizează clasele P, NP, co-NP la calcule oracol .

Definiție

Există multe definiții echivalente ale claselor ierarhice polinomiale. Să luăm una dintre ele.

Pentru a defini un oracol într-o ierarhie polinomială, definim

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

unde P este mulțimea problemelor de rezolvat în timp polinomial. Atunci pentru i ≥ 0 definim

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

Unde A B este mulțimea de probleme rezolvate de o mașină Turing din clasa A extinsă cu un oracol pentru o problemă din clasa B. De exemplu, , și este o clasă de probleme rezolvate în timp polinomial cu un oracol pentru o problemă din NP . $\Sigma _{1}^{{{\rm {P}}}}={{\rm {NP}}}},\Pi _{1}^{({\rm {P}}}}={ { \rm {coNP}}}$ $\Delta _{2}^{{{\rm {P))))={{\rm {P^{{NP))))}$

Relații între clase într-o ierarhie polinomială

Definițiile implică următoarele relații:

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

Spre deosebire de ierarhiile aritmetice și analitice, unde toate incluziunile sunt stricte, în ierarhia polinomială problema strictității este încă deschisă.

Dacă există , sau oricare , atunci ierarhia se micșorează la nivelul k : pentru toți , . În practică, aceasta înseamnă că egalitatea claselor P și NP distruge complet ierarhia polinomială. $\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))))$

Unirea tuturor claselor ierarhiei polinomiale este clasa PH .

Ierarhia polinomială este omologul (de o complexitate mai mică) ierarhiei aritmetice.

Se știe că PH este conținut în PSPACE , dar nu se știe dacă cele două clase sunt egale.

O reformulare utilă a ultimei probleme: PH = PSPACE dacă și numai dacă logica de ordinul doi nu câștigă cardinalitate suplimentară prin adăugarea unui operator de închidere tranzitivă .

Fiecare clasă din ierarhia polinomială conține probleme -complete (problemele sunt complete în ceea ce privește reducerea Karp în timpul polinomial). $\leq _{({\rm {m))))^{({\rm {P))))$