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

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

Для улучшения этой статьи по информационным технологиям желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.