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

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

В теории сложности полиномиальная иерархия — это иерархия классов сложности которая обобщает классы 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}}

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


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