Клас складності PH

Клас складності PH (від англ. polynomial hierarchy) — об'єднання всіх класів складності з поліноміальної ієрархії:

${\displaystyle {\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, що предикат належить до класу ${\displaystyle \Sigma _{k}^{p}}$ або ${\displaystyle \Pi _{k}^{p}}$. Також кажуть, що мова, розпізнавана таким предикатом (тобто множина всіх слів, на яких предикат повертає 1), належить до класу PH.

Клас PH вперше визначив ^[en].

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

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

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

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

Назвемо скінченною грою таку структуру. Є дерево, вершини якого позначено іменами двох гравців A та B (всі вершини одного рівня позначено одним і тим самим іменем, ходи чергуються), а ребра відповідають ходам гравців. Нехай дано деяке початкове слово x — початкова конфігурація гри. Тоді кількість рівнів у дереві (тобто кількість ходів) дорівнює деякій функції f від довжини x, а кожне ребро позначено словом довжини g від довжини x (ходом гравця є слово, яким позначено ребро). Є предикат ${\displaystyle R(x,w_{1}w_{2}w_{3}\dots )}$ від початкової конфігурації і послідовності ходів гравців, який визначає, хто виграв (якщо він дорівнює 1, то виграв перший гравець). Оскільки гра скінченна, то виграшна стратегія завжди існує або для першого гравця, або для другого. Назвемо гру такою, що розпізнає мову L, якщо для кожного x із L гравець A має виграшну стратегію.

Клас PH є класом усіх мов, розпізнаваних іграми, такими, що f дорівнює константі (тобто кількість ходів у грі фіксована і не залежить від довжини вхідного слова), а g є многочленом від довжини x (таким чином, з кожної вершини дерева, крім останньої, виходить з ${\displaystyle 2^{p(n)}}$ ребер, де ${\displaystyle p(n)}$ — цей многочлен).

Замкнутість

На відміну від класів поліноміальної ієрархії, що складають клас PH, про PH достеменно відомо, що він замкнутий відносно перетину, об'єднання і доповнення мов. Це означає, що якщо мови ${\displaystyle L_{1}}$ і ${\displaystyle L_{2}}$ належать PH, то мови ${\displaystyle L_{1}\cap L_{2}}$, ${\displaystyle L_{1}\cup L_{2}}$ і ${\displaystyle L_{1}^{c}}$ належать PH.

Для доказу досить пред'явити ігри, які розпізнають ці комбінації мов, якщо є ігри, які розпізнають ${\displaystyle L_{1}}$ і ${\displaystyle L_{2}}$. Для доповнення передамо право першого ходу іншому гравцеві і як предикат виграшу візьмемо ${\displaystyle \neg R_{1}}$. Для перетину візьмемо дві гри, які розпізнають ${\displaystyle L_{1}}$ та ${\displaystyle L_{2}}$такими, що кількість ходів у них однакова, а другу починає не той гравець, який робить останній хід у першій. Після цього в кожну кінцеву вершину першої гри додамо другу гру, а як предикат виграшу візьмемо ${\displaystyle R_{1}(x,\,\omega _{1})\wedge R_{2}(x,\,\omega _{2})}$, де ${\displaystyle \omega _{1}}$ і ${\displaystyle \omega _{2}}$ — розбиття всієї послідовності ходів на дві: частину, що відповідає першій грі, і частину, що відповідає другий. Для об'єднання візьмемо ігри, які розпізнають ${\displaystyle L_{1}}$ та ${\displaystyle L_{2}}$, з однаковою кількістю ходів і однаковим першим гравцем. Створимо нову вершину, відповідну другому гравцеві, і причепимо до неї одне дерево першої гри (над цим ребром напишемо слово 00…0) і решту ${\displaystyle 2^{p(n)}-1}$ ребер другої гри. Перше слово гри позначимо z, а решту послідовності слів — ${\displaystyle \omega }$, а як предикат виграшу візьмемо ${\displaystyle (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 міститься в класі ${\displaystyle \Sigma _{2}^{p}}$). Сам клас PH включений у клас PSPACE і клас P^PP (клас задач, що розв'язуються за поліноміальний час на машині Тюрінга з доступом до оракула класу PP).

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

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

Примітки

1. (1977). The polynomial-time hierarchy. Theor. Comput. Sci. 3: 1—22. doi:10.1016/0304-3975(76)90061-X. Zbl 0353.02024.