В теории сложности полиномиальная иерархия — это иерархия классов сложности, которая обобщает классы P, NP, co-NP до вычислений с оракулом .

Определение

Существует множество эквивалентных определений классов полиномиальной иерархии. Приведём одно из них.

Для определения оракула в полиномиальной иерархии определим

${\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 — множество задач, решаемых машиной Тьюринга в классе A, расширенным с помощью оракула для какой-то задачи из класса B. Например, ${\displaystyle \Sigma _{1}^{\rm {P}}={\rm {NP}},\Pi _{1}^{\rm {P}}={\rm {coNP}}}$ , и ${\displaystyle \Delta _{2}^{\rm {P}}={\rm {P^{NP}}}}$ — это класс задач, решаемых за полиномиальное время с оракулом для какой-нибудь задачи из NP .

Отношения между классами в полиномиальной иерархии

Определения предполагают следующие отношения:

${\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}}}$ . На практике это означает, что равенство классов P и NP полностью разрушает полиномиальную иерархию.

Объединение всех классов полиномиальной иерархии является классом PH .

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

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

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

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