Класс PH

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

PH = ⋃ k ∈ N ( Σ k p ∪ Π k p ) = ⋃ k ∈ N Σ k p = ⋃ k ∈ N Π k p {displaystyle {mbox{PH}}=igcup _{kin mathbb {N} }left(Sigma _{k}^{p}cup Pi _{k}^{p} ight)=igcup _{kin mathbb {N} }Sigma _{k}^{p}=igcup _{kin mathbb {N} }Pi _{k}^{p}}

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

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

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

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

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

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

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

Замкнутость

В отличие от составляющих класс PH классов полиномиальной иерархии, про PH доподлинно известно, что он замкнут относительно пересечения, объединения и дополнения языков. Это означает, что если языки L 1 {displaystyle L_{1}} и L 2 {displaystyle L_{2}} принадлежат PH, то языки L 1 ∩ L 2 {displaystyle L_{1}cap L_{2}} , L 1 ∪ L 2 {displaystyle L_{1}cup L_{2}} и L 1 c {displaystyle L_{1}^{c}} принадлежат PH.

Для доказательства достаточно предъявить игры, распознающие эти комбинации языков, если имеются игры, распознающие L 1 {displaystyle L_{1}} и L 2 {displaystyle L_{2}} . Для дополнения передадим право первого хода другому игроку и в качестве предиката выигрыша возьмём ¬ R 1 {displaystyle eg R_{1}} . Для пересечения возьмём две игры, распознающие L 1 {displaystyle L_{1}} и L 2 {displaystyle L_{2}} , такими, что количество ходов в них одинаковое, а вторую начинает не тот игрок, который делает последний ход в первой. После этого в каждую концевую вершину первой игры добавим вторую игру, а в качестве предиката выигрыша возьмём R 1 ( x , ω 1 ) ∧ R 2 ( x , ω 2 ) {displaystyle R_{1}(x,,omega _{1})wedge R_{2}(x,,omega _{2})} , где ω 1 {displaystyle omega _{1}} и ω 2 {displaystyle omega _{2}} — разбиение всей последовательности ходов на две: часть, соответствующая первой игре, и часть, соответствующая второй. Для объединения возьмём игры, распознающие L 1 {displaystyle L_{1}} и L 2 {displaystyle L_{2}} , с одинаковым количеством ходов и одинаковым первым игроком. Создадим новую вершину, соответствующую другому игроку, и прицепим к ней одно дерево первой игры (над этим ребром напишем слово 00...0) и оставшиеся 2 p ( n ) − 1 {displaystyle 2^{p(n)}-1} рёбер второй игры. Первое слово игры обозначим z, а остальную часть последовательности слов — ω {displaystyle omega } , а в качестве предиката выигрыша возьмём ( z = 00 … 0 ∧ R 1 ( x , ω ) ) ∨ ( z ≠ 00 … 0 ∧ R 2 ( x , ω ) ) {displaystyle (z=00dots 0wedge R_{1}(x,omega ))vee (z eq 00dots 0wedge R_{2}(x,omega ))} .

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

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

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

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