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

Материал из Википедии — свободной энциклопедии

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