Класс PH

Класс сложности PH (от англ. polynomial hierarchy) — объединение всех классов сложности из полиномиальной иерархии:

$\text{PH}=\underset{k\in <!--\; \in \; -->\mathbb{N}}{\bigcup <!--\; \bigcup \; -->}\left({\mathrm{\Sigma <!--\; \Sigma \; -->}}_k^p\cup <!--\; \cup \; -->{\mathrm{\Pi <!--\; \Pi \; -->}}_k^p\right)=\underset{k\in <!--\; \in \; -->\mathbb{N}}{\bigcup <!--\; \bigcup \; -->}{\mathrm{\Sigma <!--\; \Sigma \; -->}}_k^p=\underset{k\in <!--\; \in \; -->\mathbb{N}}{\bigcup <!--\; \bigcup \; -->}{\mathrm{\Pi <!--\; \Pi \; -->}}_k^p$${\mbox{PH}}=\bigcup _{k\in \mathbb {N} }\left(\Sigma _{k}^{p}\cup \Pi _{k}^{p}\right)=\bigcup _{k\in \mathbb {N} }\Sigma _{k}^{p}=\bigcup _{k\in \mathbb {N} }\Pi _{k}^{p}$

Таким образом, предикат принадлежит классу PH, если существует такое k, что предикат принадлежит классу ${\mathrm{\Sigma <!--\; \Sigma \; -->}}_k^p$$\Sigma _{k}^{p}$ или ${\mathrm{\Pi <!--\; \Pi \; -->}}_k^p$$\Pi _{k}^{p}$. Также говорят, что язык, распознаваемый таким предикатом (то есть множество всех слов, на которых предикат возвращает 1), принадлежит классу PH.

Эквивалентные определенияПравить

Логическая характеризацияПравить

Класс языков PH в точности совпадает с классом языков, выразимых с помощью логики второго порядка.

Игровая характеризацияПравить

Назовём конечной игрой следующую структуру. Имеется дерево, вершины которого помечены именами двух игроков A и B (все вершины одного уровня помечены одним и тем же именем, ходы чередуются), а рёбра соответствуют ходам игроков. Пусть дано некоторое начальное слово x — начальная конфигурация игры. Тогда количество уровней в дереве (т.е. количество ходов) равно некоторой функции f от длины x, а каждое ребро помечено словом длины g от длины x (ходом игрока является слово, которым помечено ребро). Имеется предикат $R(x,w_1{w}_2{w}_3\dots <!--\; \dots \; -->)$$R(x,w_{1}w_{2}w_{3}\dots )$  от начальной конфигурации и последовательности ходов игроков, который определяет, кто выиграл (если он равен 1, то выиграл первый игрок). Поскольку игра конечна, то выигрышная стратегия всегда существует либо у первого игрока, либо у второго. Назовём игру распознающей язык L, если для каждого слова x из L у игрока A есть выигрышная стратегия.

Класс PH является классом всех языков, распознаваемых играми, такими, что f равна константе (т.е. количество ходов в игре фиксировано и не зависит от длины входного слова), а g является многочленом от длины x (таким образом, из каждой вершины дерева, кроме последней, исходит по $2^{p(n)}$$2^{p(n)}$  рёбер, где $p(n)$$p(n)$  — этот многочлен).

ЗамкнутостьПравить

В отличие от составляющих класс PH классов полиномиальной иерархии, про PH доподлинно известно, что он замкнут относительно пересечения, объединения и дополнения языков. Это означает, что если языки $L_1$$L_{1}$  и $L_2$$L_{2}$  принадлежат PH, то языки $L_1\cap <!--\; \cap \; -->L_2$$L_{1}\cap L_{2}$ , $L_1\cup <!--\; \cup \; -->L_2$$L_{1}\cup L_{2}$  и $L_1^c$$L_{1}^{c}$  принадлежат PH.

Для доказательства достаточно предъявить игры, распознающие эти комбинации языков, если имеются игры, распознающие $L_1$$L_{1}$  и $L_2$$L_{2}$ . Для дополнения передадим право первого хода другому игроку и в качестве предиката выигрыша возьмём $\mathrm{\neg <!--\; \neg \; -->}{R}_1$$\neg R_{1}$ . Для пересечения возьмём две игры, распознающие $L_1$$L_{1}$  и $L_2$$L_{2}$ , такими, что количество ходов в них одинаковое, а вторую начинает не тот игрок, который делает последний ход в первой. После этого в каждую концевую вершину первой игры добавим вторую игру, а в качестве предиката выигрыша возьмём $R_1(x,{\mathrm{\omega <!--\; \omega \; -->}}_1)\wedge <!--\; \wedge \; -->R_2(x,{\mathrm{\omega <!--\; \omega \; -->}}_2)$$R_{1}(x,\,\omega _{1})\wedge R_{2}(x,\,\omega _{2})$ , где ${\mathrm{\omega <!--\; \omega \; -->}}_1$$\omega _{1}$  и ${\mathrm{\omega <!--\; \omega \; -->}}_2$$\omega _{2}$  — разбиение всей последовательности ходов на две: часть, соответствующая первой игре, и часть, соответствующая второй. Для объединения возьмём игры, распознающие $L_1$$L_{1}$  и $L_2$$L_{2}$ , с одинаковым количеством ходов и одинаковым первым игроком. Создадим новую вершину, соответствующую другому игроку, и прицепим к ней одно дерево первой игры (над этим ребром напишем слово 00...0) и оставшиеся $2^{p(n)}-<!--\; -\; -->1$$2^{{p(n)}}-1$  рёбер второй игры. Первое слово игры обозначим z, а остальную часть последовательности слов — $\mathrm{\omega <!--\; \omega \; -->}$$\omega$ , а в качестве предиката выигрыша возьмём $(z=00\dots <!--\; \dots \; -->0\wedge <!--\; \wedge \; -->R_1(x,\mathrm{\omega <!--\; \omega \; -->}))\vee <!--\; \vee \; -->(z\ne <!--\; \ne \; -->00\dots <!--\; \dots \; -->0\wedge <!--\; \wedge \; -->R_2(x,\mathrm{\omega <!--\; \omega \; -->}))$$(z=00\dots 0\wedge R_{1}(x,\omega ))\vee (z\neq 00\dots 0\wedge R_{2}(x,\omega ))$ .

Отношения с другими классамиПравить

 

Иерархия классов сложности.

По определению, в класс PH включены все классы полиномиальной иерархии, в том числе P и NP. Кроме того, он содержит вероятностные классы, такие как класс BPP (т.к. BPP содержится в классе ${\mathrm{\Sigma <!--\; \Sigma \; -->}}_2^p$$\Sigma _{2}^{p}$ ). Сам класс PH включён в класс PSPACE и класс P^PP (класс задач, которые решаются за полиномиальное время на машине Тьюринга с доступом к оракулу класса PP).

Открытые проблемыПравить

Установлено, что P = NP, тогда и только тогда, когда P = PH. Это утверждение может облегчить доказательство того, что P ≠ NP (если это так), поскольку нужно будет лишь отделить P от более общего класса, чем NP.