Просмотр кода страницы Класс PH

'''[[класс сложности|Класс сложности]] PH''' (от {{lang-en|polynomial hierarchy}}) — объединение всех классов сложности из [[полиномиальная иерархия|полиномиальной иерархии]]:
:<math>\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</math>

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

== Эквивалентные определения ==
=== Логическая характеризация ===

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

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

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

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

== Замкнутость ==

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

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

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

По определению, в класс PH включены все классы полиномиальной иерархии, в том числе [[класс P|P]] и [[класс NP|NP]]. Кроме того, он содержит вероятностные классы, такие как [[класс BPP]] (т.к. BPP содержится в классе <math>\Sigma^p_2</math>). Сам класс PH включён в [[класс PSPACE]] и класс P<sup>PP</sup> (класс задач, которые решаются за полиномиальное время на [[Вычисления с оракулом|машине Тьюринга с доступом к оракулу]] класса [[класс PP|PP]]).

== Открытые проблемы ==

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

{{Классы сложности}}
{{Нет ссылок|дата=13 мая 2011}}

[[Категория:Классы сложности]]