Polynomiální hierarchie

V teorii složitosti je polynomiální hierarchie hierarchií tříd složitosti, která zobecňuje třídy P, NP, co-NP na výpočty věštce .

Definice

Existuje mnoho ekvivalentních definic tříd polynomiální hierarchie. Vezměme si jeden z nich.

Abychom definovali orákulum v polynomiální hierarchii, definujeme

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

kde P je množina problémů, které mají být vyřešeny v polynomiálním čase. Potom pro i ≥ 0 definujeme

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

Kde A B je množina problémů řešených Turingovým strojem ve třídě A rozšířená o věštce pro nějaký problém ze třídy B. Například , a je třída problémů řešených v polynomiálním čase pomocí věštce pro nějaký problém z NP . $\Sigma _{1}^{{{\rm {P}}}}={{\rm {NP}}}},\Pi _{1}^{({\rm {P}}}}={ { \rm {coNP}}}$ $\Delta _{2}^{{{\rm {P))))={{\rm {P^{{NP))))}$

Vztahy mezi třídami v polynomiální hierarchii

Definice naznačují následující vztahy:

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

Na rozdíl od aritmetických a analytických hierarchií, kde jsou všechny inkluze striktní, je v polynomiální hierarchii otázka striktnosti stále otevřená.

Pokud existuje , nebo nějaká , pak se hierarchie zmenší na úroveň k : pro všechny , . V praxi to znamená, že rovnost tříd P a NP zcela zničí polynomiální hierarchii. $\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))))$

Sjednocením všech tříd polynomické hierarchie je třída PH .

Polynomiální hierarchie je protějšek (méně složitý) k aritmetické hierarchii.

Je známo, že PH je obsaženo v PSPACE , ale není známo, zda jsou tyto dvě třídy stejné.

Užitečné zopakování posledního problému: PH = PSPACE tehdy a jen tehdy , když logika druhého řádu nezíská extra mohutnost přidáním tranzitivního uzavíracího operátoru .

Každá třída v polynomiální hierarchii obsahuje -kompletní problémy (problémy jsou kompletní s ohledem na Karpovu redukci polynomiálního času). $\leq _{({\rm {m))))^{({\rm {P))))$