Русская Википедия:Полиномиальная иерархия

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

Определение

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

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

<math>\Delta_0^{\rm P} := \Sigma_0^{\rm P} := \Pi_0^{\rm P} := \mbox{P},</math>

где P — это множество задач, решаемых за полиномиальное время. Тогда для i ≥ 0 определим

<math>\Delta_{i+1}^{\rm P} := \mbox{P}^{\Sigma_i^{\rm P}}</math>

<math>\Sigma_{i+1}^{\rm P} := \mbox{NP}^{\Sigma_i^{\rm P}}</math>

<math>\Pi_{i+1}^{\rm P} := \mbox{coNP}^{\Sigma_i^{\rm P}}</math>

Где A^B — множество задач, решаемых машиной Тьюринга в классе A, расширенным с помощью оракула для какой-то задачи из класса B. Например, <math> \Sigma_1^{\rm P} = {\rm NP}, \Pi_1^{\rm P} = {\rm coNP} </math>, и <math> \Delta_2^{\rm P} = {\rm P^{NP}} </math> — это класс задач, решаемых за полиномиальное время с оракулом для какой-нибудь задачи из NP.

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

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

<math>\Sigma_i^{\rm P} \subseteq \Delta_{i+1}^{\rm P} \subseteq \Sigma_{i+1}^{\rm P}</math>

<math>\Pi_i^{\rm P} \subseteq \Delta_{i+1}^{\rm P} \subseteq \Pi_{i+1}^{\rm P}</math>

<math>\Sigma_i^{\rm P} = {\rm co}\Pi_{i}^{\rm P}</math>

В отличие от арифметических и аналитических иерархий, все включения в которых строги, в полиномиальной иерархии вопрос о строгости всё ещё открыт.

Если какой-нибудь <math>\Sigma_k^{\rm P} = \Sigma_{k+1}^{\rm P}</math>, или какой-нибудь <math>\Sigma_k^{\rm P} = \Pi_{k}^{\rm P}</math>, тогда иерархия сжимается до уровня k: для всех <math>i > k</math>, <math>\Sigma_i^{\rm P} = \Sigma_k^{\rm P}</math>. На практике это означает, что равенство классов P и NP полностью разрушает полиномиальную иерархию.

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

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

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

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

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