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

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

Визначення

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

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

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

де P — це множина задач, розв'язних за поліноміальний час. Тоді для 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}}}$

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

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

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

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

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

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

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

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

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

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

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

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