PH osztály

PH komplexitási osztály (az angol polinomi hierarchiából ) - a polinomi hierarchiából származó összes komplexitási osztály egyesítése:

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

Tehát egy predikátum a PH osztályba tartozik, ha létezik k olyan, hogy a predikátum a vagy osztályba tartozik . Azt is mondják, hogy az ilyen állítmány által felismert nyelv (vagyis az összes szó halmaza, amelyre az állítmány 1-et ad vissza) a PH osztályba tartozik. $\Sigma _{k}^{p}$ $\Pi _{k}^{p}$

Egyenértékű definíciók

Logikai jellemzés

A PH nyelvosztály pontosan megegyezik a másodrendű logikával kifejezhető nyelvek osztályával .

Játék jellemzése

A következő szerkezetet véges játéknak nevezzük. Van egy fa, amelynek csúcsai két A és B játékos nevével vannak felcímkézve (minden azonos szintű csúcs ugyanazzal a névvel van ellátva, a lépések váltakoznak), az élek pedig a játékosok lépéseinek felelnek meg. Adjunk meg néhány kezdő x szót — a játék kezdeti konfigurációját. Ekkor a fában lévő szintek száma (azaz a lépések száma) megegyezik valamilyen f hosszúságú x függvénnyel , és minden él egy g hosszúságú, x hosszúságú szóval van felcímkézve (a játékos lépése az a szó, amely az él). Van egy predikátum a kezdeti konfigurációból és a játékosok lépéssorozatából, amely meghatározza, hogy ki nyert (ha egyenlő 1-gyel, akkor az első játékos nyert). Mivel a játék véges, vagy az első játékosnak, vagy a másodiknak mindig van nyerő stratégiája. Nevezzünk egy játékot, amely felismeri az L nyelvet , ha az L - től származó x minden egyes szóhoz A játékos nyerő stratégiával rendelkezik. $R(x,w_{1}w_{2}w_{3}\dots )$

A PH osztály a játékok által felismert összes nyelv osztálya úgy, hogy f egy konstans (azaz a lépések száma a játékban rögzített, és nem függ a bemeneti szó hosszától), és g egy polinom hosszúságú. x (tehát a fa minden csúcsából, kivéve az utolsót, az élek mentén halad tovább, hol van ez a polinom). $2^{p(n)}$ $p(n)$

Bezárás

A PH osztályt alkotó polinomhierarchia osztályaitól eltérően bizonyosan ismert, hogy a PH zárt a nyelvek metszéspontja, uniója és komplementere alatt. Ez azt jelenti, hogy ha a és nyelvek a PH-hoz tartoznak, akkor a és a nyelvek a PH - hoz tartoznak. $L_{1}$ $L_{2}$ $L_{1}\sapka L_{2}$ $L_{1}\pohár L_{2}$ $L_{1}^{c}$

Ennek bizonyítására elegendő olyan játékokat bemutatni, amelyek felismerik ezeket a nyelvkombinációkat, ha vannak olyan játékok, amelyek felismerik és . A kiegészítéshez adjuk át az első lépés jogát egy másik játékosnak, és vegyük el a . A metszésponthoz vegyünk két, és felismerő játékot úgy, hogy ezekben a lépések száma azonos legyen, és a másodikat ne az kezdje, aki az elsőben az utolsó lépést teszi. Ezt követően hozzáadjuk a második játszmát az első játék minden végcsúcsához, és nyerési predikátumként vesszük , ahol és a teljes lépéssorozat két részre osztása: az első játéknak megfelelő részre és a megfelelő részre. a másodikra. Az egyesüléshez olyan játékokat veszünk, amelyek felismerik a és -t, azonos számú lépéssel és ugyanazzal az első játékossal. Hozzunk létre egy másik játékosnak megfelelő új csúcsot, és csatoljuk hozzá az első játék egyik fáját (ez fölé írjuk a 00...0 szót) és a második játék többi élét. A játék első szavát z -vel jelöljük, a szósor többi részét pedig -vel jelöljük , és a kifizetési predikátumot vesszük . $L_{1}$ $L_{2}$ $\neg R_{1}$ $L_{1}$ $L_{2}$ $R_{1}(x,\,\omega _{1})\ék R_{2}(x,\,\omega _{2})$ $\omega_{1}$ $\omega _{2}$ $L_{1}$ $L_{2}$ $2^{{p(n)}}-1$ $\omega$ $(z=00\dots 0\wedge R_{1}(x,\omega ))\vee (z\neq 00\dots 0\wedge R_{2}(x,\omega ))$

Kapcsolatok más osztályokkal

Definíció szerint a PH osztály magában foglalja a polinomhierarchia összes osztályát, beleértve a P -t és az NP -t is . Ezenkívül valószínűségi osztályokat is tartalmaz, például a BPP osztályt (mivel a BPP-t az osztály tartalmazza ). Maga a PH osztály a PSPACE osztályba és a P PP osztályba tartozik (olyan feladatok osztálya, amelyeket polinomiális időben oldanak meg egy Turing-gépen, amely hozzáféréssel rendelkezik a PP osztályú orákulumhoz ). $\Sigma _{2}^{p}$

Nyitott kérdések

Megállapítottuk, hogy P = NP akkor és csak akkor, ha P = PH. Ez az állítás megkönnyítheti annak bizonyítását, hogy P ≠ NP (ha igen), mivel P-t csak egy általánosabb osztálytól kellene elválasztani, mint az NP.

Algoritmusok összetettségi osztályai
Fénynek tekinthető	DLOGTIME AC 0 ACC 0 TC0 [ hu L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP EQP APX
Állítólag nehéz	U.P. NP NP kész co-NP társNP-teljes AM M.A. QMA PH ⊕P PP #P #P- IP_ PSPACE PSPACE-teljes
Nehéznek tartott	LEJÁRATI IDŐ NEXPTIME KIFEJEZÉS 2-EXPTIME ELEMENTARY R PR RE töltse ki újra Co-RE Co-RE-complete ÖSSZES