Класс PH

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

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

\mbox{PH} = \bigcup_{k\in\mathbb{N}} \left(\Sigma^p_k \cup \Pi^p_k\right) = \bigcup_{k\in\mathbb{N}} \Sigma^p_k = \bigcup_{k\in\mathbb{N}} \Pi^p_k

Таким образом, предикат принадлежит классу PH, если существует такое k, что предикат принадлежит классу \Sigma^p_k или \Pi^p_k. Также говорят, что язык, распознаваемый таким предикатом (то есть множество всех слов, на которых предикат возвращает 1), принадлежит классу PH.

Эквивалентные определения[править | править вики-текст]

Логическая характеризация[править | править вики-текст]

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

Игровая характеризация[править | править вики-текст]

Назовём конечной игрой следующую структуру. Имеется дерево, вершины которого помечены именами двух игроков A и B (все вершины одного уровня помечены одним и тем же именем, ходы чередуются), а рёбра соответствуют ходам игроков. Пусть дано некоторое начальное слово x — начальная конфигурация игры. Тогда количество уровней в дереве (т.е. количество ходов) равно некоторой функции f от длины x, а каждое ребро помечено словом длины g от длины x (ходом игрока является слово, которым помечено ребро). Имеется предикат R(x, w_1 w_2 w_3 \dots) от начальной конфигурации и последовательности ходов игроков, который определяет, кто выиграл (если он равен 1, то выиграл первый игрок). Поскольку игра конечна, то выигрышная стратегия всегда существует либо у первого игрока, либо у второго. Назовём игру распознающей язык L, если для каждого слова x из L у игрока A есть выигрышная стратегия.

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

Замкнутость[править | править вики-текст]

В отличие от составляющих класс PH классов полиномиальной иерархии, про PH доподлинно известно, что он замкнут относительно пересечения, объединения и дополнения языков. Это означает, что если языки L_1 и L_2 принадлежат PH, то языки L_1 \cap L_2, L_1 \cup L_2 и L_1^c принадлежат PH.

Для доказательства достаточно предъявить игры, распознающие эти комбинации языков, если имеются игры, распознающие L_1 и L_2. Для дополнения передадим право первого хода другому игроку и в качестве предиката выигрыша возьмём \neg R_1. Для пересечения возьмём две игры, распознающие L_1 и L_2, такими, что количество ходов в них одинаковое, а вторую начинает не тот игрок, который делает последний ход в первой. После этого в каждую концевую вершину первой игры добавим вторую игру, а в качестве предиката выигрыша возьмём R_1(x,\, \omega_1) \wedge R_2(x,\, \omega_2), где \omega_1 и \omega_2 — разбиение всей последовательности ходов на две: часть, соответствующая первой игре, и часть, соответствующая второй. Для объединения возьмём игры, распознающие L_1 и L_2, с одинаковым количеством ходов и одинаковым первым игроком. Создадим новую вершину, соответствующую другому игроку, и прицепим к ней одно дерево первой игры (над этим ребром напишем слово 00...0) и оставшиеся 2^{p(n)}-1 рёбер второй игры. Первое слово игры обозначим z, а остальную часть последовательности слов — \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 содержится в классе \Sigma^p_2). Сам класс PH включён в класс PSPACE и класс PPP (класс задач, которые решаются за полиномиальное время на машине Тьюринга с доступом к оракулу класса PP).

Открытые проблемы[править | править вики-текст]

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