Třída PH

Třída složitosti PH (z anglického polynomial hierarchy ) - spojení všech tříd složitosti z polynomiální hierarchie :

{\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}

Predikát tedy patří do třídy PH, pokud existuje k takové, že predikát patří do třídy nebo . Říká se také, že jazyk rozpoznávaný takovým predikátem (tedy množina všech slov, pro které predikát vrací 1) patří do třídy PH. $\Sigma _{k}^{p}$ $\Pi _{k}^{p}$

Ekvivalentní definice

Logická charakterizace

Třída jazyků PH je přesně stejná jako třída jazyků vyjádřitelných logikou druhého řádu .

Charakteristika hry

Následující strukturu nazýváme konečnou hrou . Existuje strom, jehož vrcholy jsou označeny jmény dvou hráčů A a B (všechny vrcholy stejné úrovně jsou označeny stejným jménem, tahy se střídají) a hrany odpovídají tahům hráčů. Nechť je uvedeno nějaké počáteční slovo x — počáteční konfigurace hry. Potom se počet úrovní ve stromu (tedy počet tahů) rovná nějaké funkci f délky x a každá hrana je označena slovem délky g délky x (tah hráče je slovo, které označuje hrana). Existuje predikát z počáteční konfigurace a posloupnost tahů hráčů, která určuje, kdo vyhrál (pokud je rovna 1, vyhrál první hráč). Protože hra je konečná, vítěznou strategii má vždy první nebo druhý hráč. Nazvěme hru rozpoznávající jazyk L , pokud pro každé slovo x z L má hráč A vítěznou strategii. $R(x,š_{1}š_{2}š_{3}\tečky)$

Třída PH je třída všech jazyků rozpoznávaných hrami tak, že f je konstanta (tj. počet tahů ve hře je pevný a nezávisí na délce vstupního slova) a g je polynom délky. x (tedy od každého vrcholu stromu, kromě posledního, postupuje podél hran, kde je tento polynom). $2^{p(n)}$ $p(n)$

Uzavření

Na rozdíl od tříd polynomiální hierarchie, které tvoří třídu PH, je s jistotou známo, že PH je uzavřená pod průnikem, sjednocením a doplňkem jazyků. To znamená, že pokud jazyky a patří do PH, pak jazyky a patří do PH. $L_{1}$ $L_{2}$ $L_{1}\cap L_{2}$ $L_{1}\pohár L_{2}$ $L_{1}^{c}$

Abychom to dokázali, postačí představit hry, které tyto kombinace jazyků rozpoznávají, pokud existují hry, které rozpoznávají a . Pro doplnění převedeme právo prvního tahu na jiného hráče a vezmeme . Abychom se protnuli, vezmeme dvě hry rozpoznávání a , takže počet tahů v nich je stejný a druhá nezačíná hráčem, který v první provede poslední tah. Poté přidáme druhou hru ke každému koncovému vrcholu první hry a vezmeme jako výplatní predikát , kde a je rozdělení celé sekvence tahů na dvě části: část odpovídající první hře a část odpovídající do druhého. Abychom se sjednotili, vezmeme hry, které rozpoznávají a , se stejným počtem tahů a stejným prvním hráčem. Vytvořme nový vrchol odpovídající jinému hráči a připojíme k němu jeden strom první hry (nad tuto hranu napíšeme slovo 00...0) a zbývající hrany druhé hry. První slovo hry označíme z a zbytek posloupnosti slov označíme a vezmeme jako výplatní predikát . $L_{1}$ $L_{2}$ $\neg R_{1}$ $L_{1}$ $L_{2}$ $R_{1}(x,\,\omega _{1})\klín R_{2}(x,\,\omega _{2})$ $\omega_{1}$ $\omega _{2}$ $L_{1}$ $L_{2}$ $2^{{p(n)}}-1$ $\omega$ $(z=00\tečky 0\klín R_{1}(x,\omega ))\vee (z\neq 00\tečky 0\klín R_{2}(x,\omega ))$

Vztahy s jinými třídami

Třída PH podle definice zahrnuje všechny třídy polynomické hierarchie, včetně P a NP . Kromě toho obsahuje pravděpodobnostní třídy, jako je třída BPP (protože BPP je obsažena ve třídě ). Samotná třída PH je zahrnuta do třídy PSPACE a třídy P PP (třída problémů, které se řeší v polynomiálním čase na Turingově stroji s přístupem k oracle třídy PP ). $\Sigma _{2}^{p}$

Otevřené problémy

Je stanoveno, že P = NP právě tehdy, když P = PH. Toto tvrzení může usnadnit důkaz, že P ≠ NP (pokud ano), protože by bylo nutné oddělit P od obecnější třídy, než je NP.

Třídy složitosti algoritmů
Považováno za světlo	DLOGTIME AC 0 ACC 0 TC0 [ en L SL RL NL NC SC CC P P-kompletní ZPP RP BPP BQP EQP APX
Prý to bude těžké	U.P. NP NP kompletní co-NP co-NP-kompletní AM M.A. QMA PH ⊕P PP #P #P- IP PSPACE PSPACE-complete
Považováno za obtížné	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY R PR RE RE-complete Co-RE Co-RE-complete VŠECHNY