Polynomhierarki

I beräkningskomplexitetsteori är polynomhierarkin ( kallas ibland polynom-tidhierarkin ) en hierarki av komplexitetsklasser som generaliserar klasserna NP och co-NP . Varje klass i hierarkin finns i PSPACE . Hierarkin kan definieras med hjälp av orakelmaskiner eller alternerande Turingmaskiner . Det är en resursbunden motsvarighet till den aritmetiska hierarkin och den analytiska hierarkin från matematisk logik . Föreningen av klasserna i hierarkin betecknas PH .

Klasser inom hierarkin har fullständiga problem (med avseende på polynom-tidsreduktioner ) som frågar om kvantifierade booleska formler håller, för formler med restriktioner för kvantifieringsordningen. Det är känt att jämlikhet mellan klasser på samma nivå eller på varandra följande nivåer i hierarkin skulle innebära en "kollaps" av hierarkin till den nivån.

Definitioner

Det finns flera ekvivalenta definitioner av klasserna i polynomhierarkin.

Oracle definition

För orakeldefinitionen av polynomhierarkin, definiera

$\Delta _{0}^{\mathsf {P}}:=\Sigma _{0}^{\mathsf {P}}:=\ Pi _{0}^{\mathsf {P}}:={\mathsf {P}},$

där P är mängden beslutsproblem som kan lösas i polynomtid . Sedan för i ≥ 0 definiera

$\Delta _{i+1}^{\mathsf {P}}:={\mathsf {P}}^{\Sigma _{i}^{\ mathsf {P}}}$

$\Sigma _{i+1}^{\mathsf {P}}:={\mathsf {NP}}^{\ Sigma _{i}^{\mathsf {P}}}$

$\Pi _{i+1}^{\mathsf {P}}:= {\mathsf {coNP}}^{\Sigma _{i}^{\mathsf {P}}}$

där ${\mathsf {P}}^{\rm {A}}$ är uppsättningen beslutsproblem som kan lösas i polynomtid av en Turing-maskin utökad med ett orakel för något komplett problem i klass A; klasserna ${\mathsf {NP}}^{\rm {A}}$ och ${\mathsf {coNP}}^{\rm {A}}$ är definieras analogt. Till exempel, $\Sigma _{1}^{\mathsf {P}}={\mathsf {NP}},\Pi _{1} ^{\mathsf {P}}={\mathsf {coNP}}$ , och $\Delta _{2}^{\mathsf {P}}={\mathsf {P^ {NP}}}$ är klassen av problem som kan lösas i polynomtid av en deterministisk Turing-maskin med ett orakel för något NP-komplett problem.

Kvantifierade booleska formler definition

För den existentiella/universella definitionen av polynomhierarkin, låt L vara ett språk (dvs. ett beslutsproblem , en delmängd av {0,1} ^* ), låt p vara ett polynom och definiera

$\exists ^{p}L:=\left\{x\in \{0,1\ }^{*}\ \left|\ \left(\exists w\in \{0,1\}^{\leq p(|x|)}\right)\langle x,w\rangle \in L\ eller hur\},$

där $\langle x,w\rangle \in \{0,1\}^{*}$ är någon standardkodning av paret binära strängar x och w as en enda binär sträng. Språket L representerar en uppsättning ordnade par av strängar, där den första strängen x är en medlem av $\exists ^{p}L$ , och den andra strängen w är en "kort" ( $|w|\leq p(|x|)$ ) vittne som vittnar att x är en medlem av $\exists ^{p}L$ . Med andra ord, $x\in \exists ^{p}L$ om och endast om det finns ett kort vittne w så att $\langle x,w \rangle \in L$ . Definiera på samma sätt

$\forall ^{p}L:=\left\{x\in \{0,1\} ^{*}\ \left|\ \left(\forall w\in \{0,1\}^{\leq p(|x|)}\right)\langle x,w\rangle \in L\right .\höger\}$

Observera att De Morgans lagar gäller: $\left(\exists ^{p}L\right)^{\rm {c}}=\forall ^{p}L ^{\rm {c}}$ och $\left(\forall ^{p}L\right)^{\rm {c}}=\exists ^{ p}L^{\rm {c}}$ , där L ^c är komplementet till L .

Låt C vara en klass av språk. Utöka dessa operatorer till att fungera på hela klasser av språk enligt definitionen

$\exists ^{\mathsf {P}}{\mathcal {C}}:=\left\{\exists ^{p}L\ |\ p{\text{ är ett polynom och }}L\in {\mathcal {C}}\right\}$

$\forall ^{\mathsf {P}}{\mathcal {C}}:=\left\{\forall ^{p}L\ |\ p{\text{ är ett polynom och }}L\i {\mathcal {C}}\right\}$

Återigen gäller De Morgans lagar: ${\mathsf {co}}\exists ^{\mathsf {P}}{\mathcal {C}}=\forall ^{ \mathsf {P}}{\mathsf {co}}{\mathcal {C}}$ och ${\displaystyle {\mathsf {co}}\forall ^{\mathsf { P}}{\mathcal {C}}=\exists ^{\mathsf {P}}{\mathsf {co}}{\mathcal {C}}} ,$ där ${\mathsf {co}}{\mathcal {C}}=\left\{L^{c}|L\in {\mathcal {C}}\right\}$ .

Klasserna NP och co-NP kan definieras som ${\displaystyle {\mathsf {NP}}=\exists ^{\mathsf {P}}{\mathsf {P}}} ,$ och ${\displaystyle {\mathsf {coNP}}=\forall ^{\mathsf {P}}{\mathsf {P}}} , där P är$ klassen av alla möjliga (polynom-tid) avgörbara språk. Polynomhierarkin kan definieras rekursivt som

$\Sigma _{0}^{\mathsf {P}}:=\Pi _{0}^{\mathsf {P}}:={\mathsf {P} }$

$\Sigma _{k+1}^{\mathsf {P}}:=\exists ^{\mathsf {P}}\Pi _{k }^{\mathsf {P}}$

$\Pi _{k+1}^{\mathsf {P}}:=\forall ^{\mathsf { P}}\Sigma _{k}^{\mathsf {P}}$

Observera att ${\mathsf {NP}}=\Sigma _{1}^{\mathsf {P}}$ och ${\mathsf {coNP}}=\Pi _{1}^{\mathsf {P}}$ .

Denna definition återspeglar det nära sambandet mellan polynomhierarkin och den aritmetiska hierarkin , där R och RE spelar roller analoga med P respektive NP . Den analytiska hierarkin definieras också på liknande sätt för att ge en hierarki av delmängder av de reella talen .

Alternerande Turing-maskiner definition

En alternerande Turing-maskin är en icke-deterministisk Turing-maskin med icke-slutliga tillstånd uppdelade i existentiella och universella tillstånd. Det accepterar så småningom från sin nuvarande konfiguration om: det är i ett existentiellt tillstånd och kan övergå till någon så småningom accepterande konfiguration; eller, det är i ett universellt tillstånd och varje övergång är till någon slutligen accepterande konfiguration; eller så är den i ett accepterande tillstånd.

Vi definierar $\Sigma _{k}^{\mathsf {P}}$ som den klass av språk som accepteras av en alternerande Turingmaskin i polynomtid så att initialtillståndet är ett existentiellt tillstånd och varje väg maskinen kan ta byten högst k – 1 gånger mellan existentiella och universella tillstånd. Vi definierar $\Pi _{k}^{\mathsf {P}}$ på liknande sätt, förutom att initialtillståndet är ett universellt tillstånd.

Om vi ​​utelämnar kravet på högst k – 1 växlingar mellan det existentiella och universella tillståndet, så att vi bara kräver att vår alternerande Turingmaskin körs i polynomtid, så har vi definitionen av klassen AP , som är lika med PSPACE .

Relationer mellan klasser i polynomhierarkin

Kommutativt diagram som motsvarar polynomets tidshierarki. Pilarna betecknar inkludering.

Unionen av alla klasser i polynomhierarkin är komplexitetsklassen PH .

Definitionerna antyder relationerna:

$\Sigma _{i}^{\mathsf {P}}\subseteq \Delta _{i+1}^{\mathsf {P}} \subseteq \Sigma _{i+1}^{\mathsf {P}}$

${\displaystyle \Pi _{i}^{\mathsf {P} }\subseteq \Delta _{i+1}^{\mathsf {P}}\subseteq \Pi _{i+1}^{\mathsf {P}}} Σ i$

$displaystyle \Sigma _{i}^{\mathsf {P}}={\mathsf {co}}\Pi _{i}^{\mathsf {P}}}$

Till skillnad från de aritmetiska och analytiska hierarkierna, vars inneslutningar är kända för att vara korrekta, är det en öppen fråga om någon av dessa inneslutningar är korrekta, även om det är allmänt trott att de alla är det. Om någon ${\displaystyle \Sigma _{k}^{\mathsf {P}}=\Sigma _{k+1}^{\mathsf {P}}} , eller om$ någon ${\displaystyle \Sigma _{k}^{\mathsf {P}}=\Pi _{k}^{\mathsf {P}}} , sedan kollapsar hierarkin till nivå$ k : för all $i>k$ , $\Sigma _{i}^{\mathsf {P}}=\Sigma _{k}^{\mathsf {P} }$ . I synnerhet har vi följande implikationer som involverar olösta problem:

• P = NP om och endast om P = PH .
• Om NP = co-NP så är NP = PH . ( co-NP är ${\displaystyle \Pi _{1}^{\mathsf {P}}} .$ )

Det fall där NP = PH också betecknas som en kollaps av PH till den andra nivån . Fallet P = NP motsvarar en kollaps av PH till P .

Olöst problem inom datavetenskap :

${\mathsf {P}}{\overset {?}{=}}{\mathsf {NP}}$

(fler olösta problem inom datavetenskap)

Frågan om kollaps till första nivån anses generellt vara extremt svår. De flesta forskare tror inte på en kollaps, inte ens till den andra nivån.

Relationer till andra klasser

Se även: PH (komplexitet) § Förhållande till andra klasser

Olöst problem inom datavetenskap :

${\mathsf {PH}}{\overset {?}{=}}{\mathsf {PSPACE}}$

(fler olösta problem inom datavetenskap)

Hasse diagram över komplexitetsklasser inklusive P , NP , co-NP , BPP , P/poly , PH och PSPACE

Polynomhierarkin är en analog (med mycket lägre komplexitet) av den exponentiella hierarkin och den aritmetiska hierarkin .

Det är känt att PH finns i PSPACE , men det är inte känt om de två klasserna är lika. En användbar omformulering av detta problem är att PH = PSPACE om och endast om andra ordningens logik över ändliga strukturer inte får någon ytterligare kraft från tillägget av en transitiv stängningsoperator .

Om polynomhierarkin har några fullständiga problem , har den bara ändligt många distinkta nivåer. Eftersom det finns PSPACE-kompletta problem vet vi att om PSPACE = PH måste polynomhierarkin kollapsa, eftersom ett PSPACE-komplett problem skulle vara ett $\Sigma _{k}^{\mathsf {P }}$ -komplett problem för vissa k .

Varje klass i polynomhierarkin innehåller $\leq _{\rm {m}}^{\mathsf {P}}$ -fullständiga problem (problem kompletta under polynom-tid många-en-reduktioner). Dessutom stängs varje klass i polynomhierarkin under $\leq _{\rm {m}}^{\mathsf {P}}$ -reduktioner : vilket betyder att för en klass C i hierarkin och en språk $L\in {\mathcal {C}}$ , om $A\leq _{\rm {m}}^{\mathsf {P}}L$ , sedan $A\in {\mathcal {C}}$ också. Dessa två fakta tillsammans antyder att om $K_{i}$ är ett komplett problem för ${\displaystyle \Sigma _{i}^{\mathsf {P}}},$ då $\Sigma _{i+1}^{\mathsf {P}}={\mathsf {NP}}^{K_{i}}$ och $\Pi _{i+1}^{\mathsf {P}}={\mathsf {coNP}}^{K_{i}}$ . Till exempel, $\Sigma _{2}^{\mathsf {P}}={\mathsf {NP}}^{\mathsf {SAT}}$ . Med andra ord, om ett språk definieras utifrån något orakel i C , så kan vi anta att det är definierat utifrån ett komplett problem för C . Kompletta problem fungerar därför som "representanter" för den klass som de är kompletta för.

Sipser –Lautemanns sats säger att klassen BPP finns i den andra nivån i polynomhierarkin.

Kannans sats säger att för vilken k som helst är $\Sigma _{2}$ inte inkluderad i SIZE (n ^k ).

Todas teorem säger att polynomhierarkin finns i P ^#P .

Problem

• Ett exempel på ett naturligt problem i $\Sigma _{2}^{\mathsf {P}}$ är kretsminimering : givet ett tal k och en krets A beräknar en boolesk funktion f , avgör om det finns en krets med högst k grindar som beräknar samma funktion f . Låt C vara mängden av alla booleska kretsar. Språket

  $L=\left\{\langle A,k,B,x\rangle \in {\mathcal {C}}\times \ mathbb {N} \times {\mathcal {C}}\times \{0,1\}^{*}\left|B{\text{ har högst }}k{\text{ grindar och }}A (x)=B(x)\höger.\höger\}$

  är avgörbar i polynomtid. Språket

  ${\displaystyle {\mathit {CM}}=\left\{\langle A,k\rangle \in {\mathcal {C} }\times \mathbb {N} \left|{\begin{matrix}{\text{det finns en krets }}B{\text{ med högst }}k{\text{ grindar }}\\{\text { så att }}A{\text{ och }}B{\text{ beräknar samma funktion}}\end{matrix}}\right.\right\}} är kretsminimeringsspråket$

  . ${\mathit {CM}}\in \Sigma _{2}^{\mathsf {P}}(=\exists ^{\mathsf {P }}\forall ^{\mathsf {P}}{\mathsf {P}})$ eftersom L är avgörbart i polynomtid och eftersom, givet $\langle A,k\rangle$ , $\langle A,k\rangle \in {\mathit {CM}}$ om och bara om det finns en krets B så att för alla ingångar x , $\langle A,k,B,x\rangle \in L$ .
• Ett komplett problem för $\Sigma _{k}^{\mathsf {P}}$ är tillfredsställbarheten för kvantifierade booleska formler med k – 1 alternationer av kvantifierare (förkortat QBF _k eller QSAT _k ). Detta är versionen av det booleska tillfredsställbarhetsproblemet för $\Sigma _{k}^{\mathsf {P}}$ . I det här problemet får vi en boolesk formel f med variabler uppdelade i k uppsättningar X ₁ , ..., X _k . Vi måste avgöra om det är sant att

  $\exists X_{1}\forall X_{2}\exists X_{3}\ldots f$

  Det vill säga, finns det en tilldelning av värden till variabler i X ₁ så att det för alla tilldelningar av värden i X ₂ finns en tilldelning av värden till variabler i X ₃ , ... f är sant? Varianten ovan är komplett för $\Sigma _{k}^{\mathsf {P}}$ . Varianten där den första kvantifieraren är "för alla", den andra är "finns", etc., är komplett för $\Pi _{k}^{\mathsf {P}}$ . Varje språk är en delmängd av problemet som erhålls genom att ta bort begränsningen av k – 1 alternationer, PSPACE -komplett problemet TQBF .
• En lista i Garey/Johnson-stil med problem som är kända för att vara kompletta för den andra och högre nivån i polynomhierarkin finns i detta kompendium .

Se även

• EXPTIME
• Exponentiell hierarki
• Aritmetisk hierarki

Allmänna referenser

1.   Arora, Sanjeev; Barak, Boaz (2009). Complexity Theory: A Modern Approach . Cambridge University Press. ISBN 978-0-521-42426-4 . avsnitt 1.4, "Maskiner som strängar och den universella Turing-maskinen" och 1.7, "Proof of theorem 1.9"
2. AR Meyer och LJ Stockmeyer . Ekvivalensproblemet för reguljära uttryck med kvadrering kräver exponentiellt utrymme. I Proceedings of the 13th IEEE Symposium on Switching and Automata Theory , s. 125–129, 1972. Uppsatsen som introducerade polynomhierarkin.
3. LJ Stockmeyer . Polynom-tidshierarkin . Theoretical Computer Science , vol.3, s. 1–22, 1976.
4. C. Papadimitriou . Beräkningskomplexitet. Addison-Wesley, 1994. Kapitel 17. Polynomhierarki , s. 409–438.
5.   Michael R. Garey och David S. Johnson (1979). Datorer och svårhanterlighet: En guide till teorin om NP-fullständighet . WH Freeman. ISBN 0-7167-1045-5 . Avsnitt 7.2: Polynomhierarkin, s. 161–167.