Clasa PH

Clasa de complexitate PH (din ierarhia polinomială engleză ) - unirea tuturor claselor de complexitate din ierarhia polinomială :

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

Astfel, un predicat aparține clasei PH dacă există k astfel încât predicatul să aparțină clasei sau . Se mai spune că limbajul recunoscut de un astfel de predicat (adică mulţimea tuturor cuvintelor pentru care predicatul returnează 1) aparţine clasei PH. $\Sigma _{k}^{p}$ $\Pi _{k}^{p}$

Definiții echivalente

Caracterizare logică

Clasa de limbi PH este exact aceeași cu clasa de limbi exprimabile prin logica de ordinul doi .

Caracterizarea jocului

Numim următoarea structură un joc finit . Există un arbore ale cărui vârfuri sunt etichetate cu numele a doi jucători A și B (toate vârfurile de același nivel sunt etichetate cu același nume, mutările alternează), iar marginile corespund mișcărilor jucătorilor. Să fie dat un cuvânt inițial x - configurația inițială a jocului. Apoi, numărul de niveluri din arbore (adică numărul de mișcări) este egal cu o funcție f de lungime x , iar fiecare margine este etichetată cu un cuvânt de lungime g de lungime x (mușcarea jucătorului este cuvântul care etichetează marginea). Există un predicat din configurația inițială și secvența de mișcări ale jucătorilor, care determină cine a câștigat (dacă este egal cu 1, atunci primul jucător a câștigat). Deoarece jocul este finit, fie primul jucător, fie al doilea are întotdeauna o strategie câștigătoare. Să numim un joc de recunoaștere a limbajului L dacă pentru fiecare cuvânt x din L jucătorul A are o strategie câștigătoare. $R(x,w_{1}w_{2}w_{3}\dots )$

Clasa PH este clasa tuturor limbilor recunoscute de jocuri, astfel încât f este o constantă (adică numărul de mișcări din joc este fix și nu depinde de lungimea cuvântului de intrare) și g este un polinom în lungime x (astfel, din fiecare vârf al arborelui, cu excepția ultimului, se trece de-a lungul marginilor, unde este acest polinom). $2^{p(n)}$ $p(n)$

Închidere

Spre deosebire de clasele ierarhiei polinomiale care alcătuiesc clasa PH, se știe cu siguranță că PH este închisă sub intersecția, uniunea și complementul limbilor. Aceasta înseamnă că, dacă limbile și aparțin PH, atunci limbile și aparțin PH. $L_{1}$ $L_{2}$ $L_{1}\cap L_{2}$ $L_{1}\cup L_{2}$ $L_{1}^{c}$

Pentru a dovedi, este suficient să prezentăm jocuri care recunosc aceste combinații de limbi, dacă există jocuri care recunosc și . Pentru complement, să transferăm dreptul de la prima mutare către alt jucător și să luăm . Pentru a se intersecta, luăm două jocuri recunoscând și , astfel încât numărul de mișcări din ele să fie același, iar al doilea nu începe de jucătorul care face ultima mutare în prima. După aceea, adăugăm cel de-al doilea joc la fiecare vârf final al primului joc și luăm ca predicat de plată , unde și este împărțirea întregii secvențe de mișcări în două părți: partea corespunzătoare primului joc și partea corespunzătoare. la al doilea. Pentru a ne uni, luăm jocuri care recunosc și , cu același număr de mutări și același prim jucător. Să creăm un nou vârf corespunzător altui jucător și să-i atașăm un arbore din primul joc (scriem cuvântul 00...0 deasupra acestei margini) și marginile rămase ale celui de-al doilea joc. Notăm primul cuvânt al jocului cu z , iar restul secvenței de cuvinte cu , și luăm ca predicat de plată . $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}$ $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 ))$

Relații cu alte clase

Prin definiție, clasa PH include toate clasele ierarhiei polinomiale, inclusiv P și NP . În plus, conține clase probabilistice, cum ar fi clasa BPP (deoarece BPP este conținut în clasa ). Clasa PH în sine este inclusă în clasa PSPACE și clasa P PP (o clasă de probleme care sunt rezolvate în timp polinomial pe o mașină Turing cu acces la oracolul clasei PP ). $\Sigma _{2}^{p}$

Probleme deschise

Se stabileşte că P = NP dacă şi numai dacă P = PH. Această afirmație poate face mai ușor să se demonstreze că P ≠ NP (dacă da), deoarece ar fi necesar doar să se separe P dintr-o clasă mai generală decât NP.

Clasele de complexitate ale algoritmilor
Considerată ușoară	DLOGTIME AC 0 ACC 0 TC0 [ en L SL RL NL NC SC CC P P-complet ZPP RP BPP BQP EQP APX
Ar trebui să fie dificil	U.P. NP NP complet co-NP co-NP-complet AM M.A._ QMA PH ⊕P PP #P #P IP PSPACE PSPACE-complete
Considerat dificil	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTAR R PR RE RE-completare Co-RE Co-RE-complete TOATE