Polynomiální hierarchie - Polynomial hierarchy

v teorie výpočetní složitosti, polynomiální hierarchie (někdy nazývaný polynomiální časová hierarchie) je hierarchie z třídy složitosti které zobecňují třídy NP a co-NP.^[1] Každá třída v hierarchii je obsažena uvnitř PSPACE. Hierarchii lze definovat pomocí věštecké stroje nebo střídavé Turingovy stroje. Jedná se o protějšek ohraničený zdroji aritmetická hierarchie a analytická hierarchie z matematická logika. Spojení tříd v hierarchii je označeno PH.

Třídy v hierarchii mají úplné problémy (s ohledem na redukce polynomiálního času ), kteří se ptají, zda kvantifikované booleovské vzorce pozdržet, pro vzorce s omezeními na pořadí kvantifikátoru. Je známo, že rovnost mezi třídami na stejné úrovni nebo po sobě jdoucích úrovních v hierarchii by znamenala „kolaps“ hierarchie na tuto úroveň.

Definice

Existuje několik ekvivalentních definic tříd polynomiální hierarchie.

Definice Oracle

Pro definici věštce hierarchie polynomů definujte

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

kde P je sada rozhodovací problémy řešitelný v polynomiální čas. Pak pro i ≥ 0 definujte

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

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

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

kde ${ displaystyle { mathsf {P}} ^ { rm {A}}}$ je sada rozhodovací problémy řešitelný v polynomiálním čase a Turingův stroj rozšířený o věštec pro nějaký úplný problém ve třídě A; třídy ${ displaystyle { mathsf {NP}} ^ { rm {A}}}$ a ${ displaystyle { mathsf {coNP}} ^ { rm {A}}}$ jsou definovány analogicky. Například, ${ displaystyle Sigma _ {1} ^ { mathsf {P}} = { mathsf {NP}}, Pi _ {1} ^ { mathsf {P}} = { mathsf {coNP}}}$ , a ${ displaystyle Delta _ {2} ^ { mathsf {P}} = { mathsf {P ^ {NP}}}}$ je třída problémů řešitelných v polynomiálním čase s věštcem pro nějaký NP-úplný problém.^[2]

Definice kvantifikovaných booleovských vzorců

Pro existenciální / univerzální definici polynomiální hierarchie, let $L$ být Jazyk (tj rozhodovací problém, podmnožina {0,1}^*), nechť $p$ být polynomiální a definovat

{ displaystyle existuje ^ {p} L: = vlevo {x v {0,1 } ^ {*} vlevo | vlevo ( existuje w v {0,1 } ^ { leq p (| x |)} right) langle x, w rangle in L right. right },}

kde ${ displaystyle langle x, w rangle in {0,1 } ^ {*}}$ je nějaké standardní kódování dvojice binárních řetězců X a w jako jeden binární řetězec. L představuje sadu uspořádaných párů řetězců, kde první řetězec X je členem ${ displaystyle existuje ^ {p} L}$ a druhý řetězec w je „short“ ( ${ displaystyle | w | leq p (| x |)}$ ) svědek svědčící o tom X je členem ${ displaystyle existuje ^ {p} L}$ . Jinými slovy, ${ displaystyle x in existuje ^ {p} L}$ jen tehdy, pokud existuje krátký svědek w takhle ${ displaystyle langle x, w rangle v L}$ . Podobně definujte

{ displaystyle 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. right }}

Všimněte si, že De Morganovy zákony držet: ${ displaystyle left ( existuje ^ {p} L vpravo) ^ { rm {c}} = pro všechny ^ {p} L ^ { rm {c}}}$ a ${ displaystyle left ( forall ^ {p} L right) ^ { rm {c}} = existuje ^ {p} L ^ { rm {c}}}$ , kde L^C je doplňkem L.

Nechat C být třídou jazyků. Podle definice rozšířte tyto operátory tak, aby fungovaly na celých jazycích

{ displaystyle existuje ^ { mathsf {P}} { mathcal {C}}: = left { existuje ^ {p} L | p { text {je polynom a}} L v { mathcal {C}} doprava }}

{ displaystyle forall ^ { mathsf {P}} { mathcal {C}}: = left { forall ^ {p} L | p { text {je polynom a}} L v { mathcal {C}} doprava }}

Zákony De Morgana opět platí: ${ displaystyle { mathsf {co}} existuje ^ { mathsf {P}} { mathcal {C}} = forall ^ { mathsf {P}} { mathsf {co}} { mathcal {C }}}$ a ${ displaystyle { mathsf {co}} forall ^ { mathsf {P}} { mathcal {C}} = existuje ^ { mathsf {P}} { mathsf {co}} { mathcal {C }}}$ , kde ${ displaystyle { mathsf {co}} { mathcal {C}} = vlevo {L ^ {c} | L v { mathcal {C}} vpravo }}$ .

Třídy NP a co-NP lze definovat jako ${ displaystyle { mathsf {NP}} = existuje ^ { mathsf {P}} { mathsf {P}}}$ , a ${ displaystyle { mathsf {coNP}} = forall ^ { mathsf {P}} { mathsf {P}}}$ , kde P je třída všech proveditelných (polynomiálně) rozhodovatelných jazyků. Polynomiální hierarchii lze definovat rekurzivně jako

{ displaystyle Sigma _ {0} ^ { mathsf {P}}: = Pi _ {0} ^ { mathsf {P}}: = { mathsf {P}}}

{ displaystyle Sigma _ {k + 1} ^ { mathsf {P}}: = existuje ^ { mathsf {P}} Pi _ {k} ^ { mathsf {P}}}

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

Všimněte si, že ${ displaystyle { mathsf {NP}} = Sigma _ {1} ^ { mathsf {P}}}$ , a ${ displaystyle { mathsf {coNP}} = Pi _ {1} ^ { mathsf {P}}}$ .

Tato definice odráží úzké spojení mezi polynomiální hierarchií a aritmetická hierarchie, kde R a RE hrát role analogicky k P a NP, resp. The analytická hierarchie je také definován podobným způsobem, aby hierarchii podmnožin reálných čísel.

Definice střídavých Turingových strojů

An střídavý Turingův stroj je nedeterministický Turingův stroj s nedefinálními stavy rozdělenými do existenčních a univerzálních stavů. Nakonec přijímá ze své aktuální konfigurace, pokud: je v existenčním stavu a může přejít do nějaké nakonec přijímající konfigurace; nebo je v univerzálním stavu a každý přechod je do nějaké nakonec přijímající konfigurace; nebo je v přijímajícím stavu.^[3]

Definujeme ${ displaystyle Sigma _ {k} ^ { mathsf {P}}}$ být třídou jazyků přijímaných střídavým Turingovým strojem v polynomiálním čase tak, že počáteční stav je existenční stav a každá cesta, kterou stroj může nanejvýš vyměnit k - 1krát mezi existenčními a univerzálními státy. Definujeme ${ displaystyle Pi _ {k} ^ { mathsf {P}}}$ podobně, kromě toho, že počáteční stav je univerzální stav.^[4]

Pokud vynecháme požadavek maximálně k - 1 swapy mezi existenciálním a univerzálním stavem, takže vyžadujeme pouze to, aby náš střídavý Turingův stroj běžel v polynomiálním čase, pak máme definici třídy AP, což se rovná PSPACE.^[5]

Vztahy mezi třídami v polynomiální hierarchii

Komutativní diagram ekvivalentní polynomiální časové hierarchii. Šipky označují zařazení.

Spojením všech tříd v polynomiální hierarchii je třída složitosti PH.

Definice znamenají vztahy:

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

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

Na rozdíl od aritmetických a analytických hierarchií, o jejichž inkluzích je známo, že jsou správné, je otevřenou otázkou, zda je některá z těchto inkluzí správná, i když se obecně věří, že všechny jsou. Jestli nějaký ${ displaystyle Sigma _ {k} ^ { mathsf {P}} = Sigma _ {k + 1} ^ { mathsf {P}}}$ , nebo pokud existují ${ displaystyle Sigma _ {k} ^ { mathsf {P}} = Pi _ {k} ^ { mathsf {P}}}$ , pak hierarchie zhroutí se na úroveň k: pro všechny ${ displaystyle i> k}$ , ${ displaystyle Sigma _ {i} ^ { mathsf {P}} = Sigma _ {k} ^ { mathsf {P}}}$ .^[6] Máme zejména následující důsledky týkající se nevyřešených problémů:

P = NP kdyby a jen kdyby P = PH.^[7]
Li NP = co-NP pak NP = PH. (co-NP je ${ displaystyle Sigma _ {1} ^ { mathsf {P}}}$ .)

Vztahy k jiným třídám

Nevyřešený problém v informatice:

{ displaystyle { mathsf {PH}} { přesahující {?} {=}} { mathsf {PSPACE}}}

(více nevyřešených problémů v informatice)

Polynomiální hierarchie je analogií (při mnohem menší složitosti) exponenciální hierarchie a aritmetická hierarchie.

Je známo, že PH je obsažen uvnitř PSPACE, ale není známo, zda jsou obě třídy stejné. Jedním z užitečných přeformulování tohoto problému je, že PH = PSPACE právě tehdy logika druhého řádu nad konečnými strukturami nezíská žádnou další sílu přidáním a přechodné uzavření operátor.

Pokud má polynomiální hierarchie nějakou úplné problémy, pak má jen konečně mnoho odlišných úrovní. Protože tam jsou PSPACE - kompletní problémy, víme, že pokud PSPACE = PH, musí se polynomiální hierarchie zhroutit, protože problém s PSPACE by byl ${ displaystyle Sigma _ {k} ^ { mathsf {P}}}$ -kompletní problém pro některé k.^[8]

Každá třída v polynomiální hierarchii obsahuje ${ displaystyle leq _ { rm {m}} ^ { mathsf {P}}}$ -kompletní problémy (problémy dokončené v polynomiálním čase mnoho-jedna redukce). Kromě toho je každá třída v polynomiální hierarchii uzavřeno pod ${ displaystyle leq _ { rm {m}} ^ { mathsf {P}}}$ -redukce: to znamená pro třídu C v hierarchii a jazyk ${ displaystyle L v { mathcal {C}}}$ , pokud ${ displaystyle A leq _ { rm {m}} ^ { mathsf {P}} L}$ , pak ${ displaystyle A v { mathcal {C}}}$ také. Tyto dvě skutečnosti společně naznačují, že pokud ${ displaystyle K_ {i}}$ je úplný problém pro ${ displaystyle Sigma _ {i} ^ { mathsf {P}}}$ , pak ${ displaystyle Sigma _ {i + 1} ^ { mathsf {P}} = { mathsf {NP}} ^ {K_ {i}}}$ , a ${ displaystyle Pi _ {i + 1} ^ { mathsf {P}} = { mathsf {coNP}} ^ {K_ {i}}}$ . Například, ${ displaystyle Sigma _ {2} ^ { mathsf {P}} = { mathsf {NP}} ^ { mathsf {SAT}}}$ . Jinými slovy, pokud je jazyk definován na základě nějakého věštce v C, pak můžeme předpokládat, že je definován na základě úplného problému pro C. Úplné problémy proto fungují jako „zástupci“ třídy, pro kterou jsou úplní.

The Sipser – Lautemannova věta uvádí, že třída BPP je obsažen ve druhé úrovni polynomiální hierarchie.

Kannanova věta uvádí, že pro všechny k, ${ displaystyle Sigma _ {2}}$ není obsažen v VELIKOST(č^k).

Todova věta uvádí, že polynomiální hierarchie je obsažena v P^#P.

Problémy

Příklad přirozeného problému v ${ displaystyle Sigma _ {2} ^ { mathsf {P}}}$ je minimalizace obvodu: dostal číslo k a obvod A výpočetní technika a Booleovská funkce F, určete, zda existuje obvod s maximálně k brány, které počítají stejnou funkci F. Nechat C být množinou všech booleovských obvodů. Jazyk
${ displaystyle L = left { langle A, k, B, x rangle in { mathcal {C}} times mathbb {N} times { mathcal {C}} times {0 , 1 } ^ {*} left | B { text {má maximálně}} k { text {brány, a}} A (x) = B (x) right. Right }}$
je rozhodnutelný v polynomiálním čase. Jazyk
${ displaystyle { mathit {CM}} = left { langle A, k rangle in { mathcal {C}} times mathbb {N} left | { begin {matrix} { text {existuje obvod}} B { text {s maximálně}} k { text {brány}} { text {takový, že}} A { text {a}} B { text {vypočítat stejná funkce}} end {matrix}} right. right }}$
je jazyk pro minimalizaci obvodu. ${ displaystyle { mathit {CM}} in Sigma _ {2} ^ { mathsf {P}} (= existuje ^ { mathsf {P}} forall ^ { mathsf {P}} { mathsf {P}})}$ protože $L$ je rozhodnutelný v polynomiálním čase a protože, daný ${ displaystyle langle A, k rangle}$ , ${ displaystyle langle A, k rangle in { mathit {CM}}}$ kdyby a jen kdyby tady existuje obvod $B$ takhle pro všechny vstupy $X$ , ${ displaystyle langle A, k, B, x rangle v L}$ .
Úplný problém pro ${ displaystyle Sigma _ {k} ^ { mathsf {P}}}$ je uspokojivost pro kvantifikované booleovské vzorce s k - 1 střídání kvantifikátorů (zkráceně QBF_k nebo QSAT_k). Toto je verze booleovský problém uspokojivosti pro ${ displaystyle Sigma _ {k} ^ { mathsf {P}}}$ . V tomto problému dostáváme booleovský vzorec F s proměnnými rozdělenými do k sady X₁, ..., X_k. Musíme zjistit, zda je to pravda
${ displaystyle existuje X_ {1} celkem X_ {2} existuje X_ {3} ldots f}$
To znamená, že existuje přiřazení hodnot k proměnným v X₁ takové, že pro všechna přiřazení hodnot v X₂, v proměnných existuje přiřazení hodnot k proměnným X₃, ... F je pravda? Výše uvedená varianta je kompletní pro ${ displaystyle Sigma _ {k} ^ { mathsf {P}}}$ . Varianta, ve které je první kvantifikátor „pro všechny“, druhý je „existuje“ atd., Je úplná pro ${ displaystyle Pi _ {k} ^ { mathsf {P}}}$ . Každý jazyk je podmnožinou problému získaného odstraněním omezení k - 1 střídání, PSPACE-úplný problém TQBF.
Seznam problémů ve stylu Garey / Johnson, o nichž je známo, že jsou pro druhou a vyšší úrovně polynomiální hierarchie úplné, najdete v toto kompendium.

Viz také

Reference

^ Arora a Barak, 2009, s. 97
^ Úplnost v hierarchii polynomiálního času A Kompendium, M. Schaefer, C. Umans
^ Arora a Barak, str. 99–100
^ Arora a Barak, str. 100
^ Arora a Barak, str. 100
^ Arora a Barak, 2009, Věta 5.4
^ Hemaspaandra, Lane (2018). „17.5 Třídy složitosti“. V Rosen, Kenneth H. (ed.). Příručka diskrétní a kombinatorické matematiky. Diskrétní matematika a její aplikace (2. vyd.). CRC Press. str. 1308–1314. ISBN 9781351644051.
^ Arora a Barak, 2009, nárok 5.5

Obecné odkazy

Arora, Sanjeev; Barak, Boaz (2009). Teorie složitosti: moderní přístup. Cambridge University Press. ISBN 978-0-521-42426-4. část 1.4, „Stroje jako struny a univerzální Turingův stroj“ a 1.7, „Důkaz věty 1.9“
A. R. Meyer a L. J. Stockmeyer. Problém ekvivalence pro regulární výrazy se čtvercem vyžaduje exponenciální prostor. Ve sborníku 13. IEEE Symposium on Switching and Automata Theory, s. 125–129, 1972. Příspěvek představující polynomiální hierarchii.
L. J. Stockmeyer. Hierarchie polynomiálního času. Teoretická informatika, sv. 3, s. 1–22, 1976.
C. Papadimitriou. Výpočetní složitost. Addison-Wesley, 1994. Kapitola 17. Polynomiální hierarchie, str. 409–438.
Michael R. Garey a David S. Johnson (1979). Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti. W.H. Freemane. ISBN 0-7167-1045-5. Sekce 7.2: Polynomiální hierarchie, s. 161–167.

Citace

[1] Arora a Barak, 2009, s. 97

[2] Úplnost v hierarchii polynomiálního času A Kompendium, M. Schaefer, C. Umans

[3] Arora a Barak, str. 99–100

[4] Arora a Barak, str. 100

[5] Arora a Barak, str. 100

[6] Arora a Barak, 2009, Věta 5.4

[7] Hemaspaandra, Lane (2018). „17.5 Třídy složitosti“. V Rosen, Kenneth H. (ed.). Příručka diskrétní a kombinatorické matematiky. Diskrétní matematika a její aplikace (2. vyd.). CRC Press. str. 1308–1314. ISBN 9781351644051.

[8] Arora a Barak, 2009, nárok 5.5

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Důležité třídy složitosti (více )
Považováno za proveditelné	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-kompletní ZPP RP BPP BQP APX
Podezření na nemožnost	NAHORU NP NP-kompletní NP-tvrdé co-NP co-NP-kompletní DOPOLEDNE QMA PH ⊕P PP #P # P-kompletní IP PSPACE PSPACE - kompletní
Považováno za neproveditelné	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ZÁKLADNÍ PR R RE VŠECHNO
Hierarchie tříd	Polynomiální hierarchie Exponenciální hierarchie Grzegorczykova hierarchie Aritmetická hierarchie Booleovská hierarchie
Rodiny tříd	DTIME NTIME DSPACE NSPACE Pravděpodobně ověřitelný důkaz Interaktivní kontrolní systém