Polinomiális hierarchia

A komplexitáselméletben a polinomiális hierarchia a komplexitási osztályok hierarchiája, amely a P, NP, co-NP osztályokat általánosítja az orákulum-számításokra .

Definíció

A polinomiális hierarchia osztályoknak sok egyenértékű definíciója létezik. Vegyünk közülük egyet.

Egy orákulum polinomiális hierarchiában való meghatározásához definiáljuk

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

ahol P a polinomiális időben megoldandó feladatok halmaza. Ekkor i ≥ 0 esetén definiáljuk

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

Ahol A B az A osztályba tartozó Turing-gép által megoldott problémák halmaza, kibővítve egy orákulummal a B osztály valamelyik problémájára. Például , és olyan feladatok osztálya, amelyeket polinomiális időben egy orákulumban oldanak meg az NP valamelyik problémájára . $\Sigma _{1}^{{{\rm {P}}}}={{\rm {NP}}}},\Pi _{1}^{({\rm {P}}}}={ { \rm {coNP}}}$ $\Delta _{2}^{{{\rm {P))))={{\rm {P^{{NP))))}$

Osztályok közötti kapcsolatok polinomiális hierarchiában

A definíciók a következő összefüggésekre utalnak:

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

Ellentétben az aritmetikai és analitikus hierarchiával, ahol minden zárvány szigorú, a polinomiális hierarchiában a szigorúság kérdése továbbra is nyitott.

Ha van ilyen , vagy bármilyen , akkor a hierarchia k szintre zsugorodik : mindenkinek , . A gyakorlatban ez azt jelenti, hogy a P és NP osztályok egyenlősége teljesen lerombolja a polinomiális hierarchiát. $\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))))$

A polinomhierarchia összes osztályának uniója a PH osztály .

A polinomiális hierarchia az aritmetikai hierarchia megfelelője (kevésbé bonyolult).

Ismeretes, hogy a PH -t a PSPACE tartalmazza , de nem ismert, hogy a két osztály egyenlő-e.

Az utolsó probléma hasznos újrafogalmazása: PH = PSPACE akkor és csak akkor, ha a másodrendű logika nem nyer extra kardinalitást egy tranzitív lezáró operátor hozzáadásával .

A polinomi hierarchia minden osztálya -complete problémákat tartalmaz (a problémák teljesek a polinomidőben Karp redukciójával kapcsolatban ). $\leq _{({\rm {m))))^{({\rm {P))))$