В теорії алгоритмів класом складності 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.


1. Еквівалентні визначення

1.1. Логічна характеризація

Клас мов PH в точності збігається з класом мов, виразність за допомогою логіки другого порядку.

1.2. Ігрова характеризація

Назвемо кінцевої грою наступну структуру. Мається дерево, вершини якого позначені іменами двох гравців 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) - Цей многочлен).


2. Замкнутість

На відміну від складових клас PH класів полиномиальной ієрархії, про PH достеменно відомо, що він замкнутий щодо перетину, об'єднання і доповнення мов. Це означає, що якщо мови L_1 і L_1 належать 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)) .


3. Відносини з іншими класами

За визначенням, в клас PH включені всі класи полиномиальной ієрархії, у тому числі P і NP. Крім того, він містить імовірнісні класи, такі як клас BPP (тому BPP міститься в класі \ Sigma ^ p_2 ). Сам клас PH включений в клас PSPACE і клас P PP (клас задач, які вирішуються за поліноміальний час на машині Тьюринга з доступом до оракула класу PP).


4. Відкриті проблеми

Встановлено, що P = NP, якщо і тільки якщо P = PH. Це твердження може полегшити доказ того, що P ≠ NP (якщо це так), оскільки потрібно буде лише відокремити P від ​​більш загального класу, ніж NP.

Вважається легкими P L NL AC NC P-complete BQP BPP RP ZPP
Предпологаются складними NP ( co-NP NP-Complete Co-NP-complete) UP # P (# P-complete) IP PSPACE (PSPACE-complete) R PP AM
Вважається складними EXPTIME NEXPTIME EXPSPACE 2-EXPTIME PR RE Co-RE RE-complete Co-RE-complete PH
Список алгоритмів