Полиномиальная иерархия

В теории сложности полиномиальная иерархия — это иерархия классов сложности, которая обобщает классы 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 — множество задач, решаемых машиной Тьюринга в классе A, расширенным с помощью оракула для какой-то задачи из класса 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.

Полиномиальная иерархия является аналогом (меньшей сложности) для арифметической иерархии.

Известно, что PH содержится в PSPACE, но не известно равны ли эти два класса.

• Полезная переформулировка последней задачи: PH = PSPACE тогда и только тогда, когда логика второго порядка не получает дополнительной мощности при добавлении оператора транзитивного замыкания.

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