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

В теории сложности полиномиальная иерархия — это иерархия классов сложности, которая обобщает классы 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}}}$-полные задачи (задачи полны относительно сведения по Карпу за полиномиальное время).

Эта страница в последний раз была отредактирована 28 апреля 2016 в 20:22.