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

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

ОпределениеПравить

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

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

${\mathrm{\Delta <!--\; \Delta \; -->}}_0^{\mathrm{P}}:={\mathrm{\Sigma <!--\; \Sigma \; -->}}_0^{\mathrm{P}}:={\mathrm{\Pi <!--\; \Pi \; -->}}_0^{\mathrm{P}}:=\text{P},$$\Delta _{0}^{{{\rm {P}}}}:=\Sigma _{0}^{{{\rm {P}}}}:=\Pi _{0}^{{{\rm {P}}}}:={\mbox{P}},$ 

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

${\mathrm{\Delta <!--\; \Delta \; -->}}_{i+1}^{\mathrm{P}}:={\text{P}}^{{\mathrm{\Sigma <!--\; \Sigma \; -->}}_i^{\mathrm{P}}}$$\Delta _{{i+1}}^{{{\rm {P}}}}:={\mbox{P}}^{{\Sigma _{i}^{{{\rm {P}}}}}}$ 

${\mathrm{\Sigma <!--\; \Sigma \; -->}}_{i+1}^{\mathrm{P}}:={\text{NP}}^{{\mathrm{\Sigma <!--\; \Sigma \; -->}}_i^{\mathrm{P}}}$$\Sigma _{{i+1}}^{{{\rm {P}}}}:={\mbox{NP}}^{{\Sigma _{i}^{{{\rm {P}}}}}}$ 

${\mathrm{\Pi <!--\; \Pi \; -->}}_{i+1}^{\mathrm{P}}:={\text{coNP}}^{{\mathrm{\Sigma <!--\; \Sigma \; -->}}_i^{\mathrm{P}}}$$\Pi _{{i+1}}^{{{\rm {P}}}}:={\mbox{coNP}}^{{\Sigma _{i}^{{{\rm {P}}}}}}$ 

Где A^B — множество задач, решаемых машиной Тьюринга в классе A, расширенным с помощью оракула для какой-то задачи из класса B. Например, ${\mathrm{\Sigma <!--\; \Sigma \; -->}}_1^{\mathrm{P}}=\mathrm{N}\mathrm{P},{\mathrm{\Pi <!--\; \Pi \; -->}}_1^{\mathrm{P}}=\mathrm{c}\mathrm{o}\mathrm{N}\mathrm{P}$$\Sigma _{1}^{{{\rm {P}}}}={{\rm {NP}}},\Pi _{1}^{{{\rm {P}}}}={{\rm {coNP}}}$ , и ${\mathrm{\Delta <!--\; \Delta \; -->}}_2^{\mathrm{P}}={\mathrm{P}}^{\mathrm{N}\mathrm{P}}$$\Delta _{2}^{{{\rm {P}}}}={{\rm {P^{{NP}}}}}$  — это класс задач, решаемых за полиномиальное время с оракулом для какой-нибудь задачи из NP.

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

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

${\mathrm{\Sigma <!--\; \Sigma \; -->}}_i^{\mathrm{P}}\subseteq <!--\; \subseteq \; -->{\mathrm{\Delta <!--\; \Delta \; -->}}_{i+1}^{\mathrm{P}}\subseteq <!--\; \subseteq \; -->{\mathrm{\Sigma <!--\; \Sigma \; -->}}_{i+1}^{\mathrm{P}}$$\Sigma _{i}^{{{\rm {P}}}}\subseteq \Delta _{{i+1}}^{{{\rm {P}}}}\subseteq \Sigma _{{i+1}}^{{{\rm {P}}}}$ 

${\mathrm{\Pi <!--\; \Pi \; -->}}_i^{\mathrm{P}}\subseteq <!--\; \subseteq \; -->{\mathrm{\Delta <!--\; \Delta \; -->}}_{i+1}^{\mathrm{P}}\subseteq <!--\; \subseteq \; -->{\mathrm{\Pi <!--\; \Pi \; -->}}_{i+1}^{\mathrm{P}}$$\Pi _{i}^{{{\rm {P}}}}\subseteq \Delta _{{i+1}}^{{{\rm {P}}}}\subseteq \Pi _{{i+1}}^{{{\rm {P}}}}$ 

${\mathrm{\Sigma <!--\; \Sigma \; -->}}_i^{\mathrm{P}}=\mathrm{c}\mathrm{o}{\mathrm{\Pi <!--\; \Pi \; -->}}_i^{\mathrm{P}}$$\Sigma _{i}^{{{\rm {P}}}}={{\rm {co}}}\Pi _{{i}}^{{{\rm {P}}}}$ 

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

Если какой-нибудь ${\mathrm{\Sigma <!--\; \Sigma \; -->}}_k^{\mathrm{P}}={\mathrm{\Sigma <!--\; \Sigma \; -->}}_{k+1}^{\mathrm{P}}$$\Sigma _{k}^{{{\rm {P}}}}=\Sigma _{{k+1}}^{{{\rm {P}}}}$ , или какой-нибудь ${\mathrm{\Sigma <!--\; \Sigma \; -->}}_k^{\mathrm{P}}={\mathrm{\Pi <!--\; \Pi \; -->}}_k^{\mathrm{P}}$$\Sigma _{k}^{{{\rm {P}}}}=\Pi _{{k}}^{{{\rm {P}}}}$ , тогда иерархия сжимается до уровня k: для всех $i>k$$i>k$ , ${\mathrm{\Sigma <!--\; \Sigma \; -->}}_i^{\mathrm{P}}={\mathrm{\Sigma <!--\; \Sigma \; -->}}_k^{\mathrm{P}}$$\Sigma _{i}^{{{\rm {P}}}}=\Sigma _{k}^{{{\rm {P}}}}$ . На практике это означает, что равенство классов P и NP полностью разрушает полиномиальную иерархию.

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

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

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

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

Каждый класс в полиномиальной иерархии содержит ${\le <!--\; \le \; -->}_{\mathrm{m}}^{\mathrm{P}}$$\leq _{{{\rm {m}}}}^{{{\rm {P}}}}$ -полные задачи (задачи полны относительно сведения по Карпу за полиномиальное время).