Поліноміальна ієрархія

У теорії складності поліноміальна ієрархія — це ієрархія класів складності, яка узагальнює класи P, NP, co-NP^[1] до обчислень з оракулом.

Визначення

Існує багато еквівалентних визначень класів поліноміальної ієрархії. Наведемо одне з них.

Для визначення оракула в поліноміальній ієрархії визначимо

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

де P — це множина задач, розв'язних за поліноміальний час. Тоді для i ≥ 0 визначимо

${\displaystyle \Delta _{i+1}^{\rm {P}}:={\mbox{P}}^{\Sigma _{i}^{\rm {P}}}}$

${\displaystyle \Sigma _{i+1}^{\rm {P}}:={\mbox{NP}}^{\Sigma _{i}^{\rm {P}}}}$

${\displaystyle \Pi _{i+1}^{\rm {P}}:={\mbox{coNP}}^{\Sigma _{i}^{\rm {P}}}}$

де A^B — множина задач вибору, що вирішуються за поліноміальний час машиною Тьюринга, розширеною за допомогою оракула для якоїсь задачі з класу B. Наприклад, ${\displaystyle \Sigma _{1}^{\rm {P}}={\rm {NP}},\Pi _{1}^{\rm {P}}={\rm {coNP}}}$, і ${\displaystyle \Delta _{2}^{\rm {P}}={\rm {P^{NP}}}}$ — це клас задач, що розв'язуються за поліноміальний час з оракулом для будь-якої задачі з NP.^[2]

Відношення між класами в поліноміальній ієрархії

Визначення припускають такі відношення:

${\displaystyle \Sigma _{i}^{\rm {P}}\subseteq \Delta _{i+1}^{\rm {P}}\subseteq \Sigma _{i+1}^{\rm {P}}}$

${\displaystyle \Pi _{i}^{\rm {P}}\subseteq \Delta _{i+1}^{\rm {P}}\subseteq \Pi _{i+1}^{\rm {P}}}$

${\displaystyle \Sigma _{i}^{\rm {P}}={\rm {co}}\Pi _{i}^{\rm {P}}}$

На відміну від арифметичних і аналітичних ієрархій, всі включення в яких строгі, в поліноміальній ієрархії питання про строгість все ще відкрите.

Якщо якийсь ${\displaystyle \Sigma _{k}^{\rm {P}}=\Sigma _{k+1}^{\rm {P}}}$, або якийсь ${\displaystyle \Sigma _{k}^{\rm {P}}=\Pi _{k}^{\rm {P}}}$, то ієрархія стискається до рівня k: для всіх ${\displaystyle i>k}$, ${\displaystyle \Sigma _{i}^{\rm {P}}=\Sigma _{k}^{\rm {P}}}$.^[3] На практиці це означає, що рівність класів P і NP повністю руйнує поліноміальну ієрархію.

Об'єднання всіх класів поліноміальної ієрархії є класом PH.

Поліноміальна ієрархія є аналогом (меншої складності) для експоненційної ієрархії^[en] та арифметичної ієрархії^[en].

Нерозв'язана проблема інформатики: ${\displaystyle {\mathsf {PH}}{\overset {?}{=}}{\mathsf {PSPACE}}}$ (більше нерозв'язаних проблем інформатики)

Відомо, що PH міститься в PSPACE, але не відомо чи рівні ці два класи.

• Корисне переформулювання останньої задачі: PH = PSPACE тоді й тільки тоді, коли логіка другого порядку не отримує додаткової потужності при додаванні оператора транзитивного замикання.

Кожен клас у поліноміальній ієрархії містить ${\displaystyle \leq _{\rm {m}}^{\rm {P}}}$-повні задачі (задачі повні відносно зведення за Карпом за поліноміальний час).