PP (složitost) - PP (complexity)

PP ve vztahu k dalším třídám pravděpodobnostní složitosti (ZPP, RP co-RP, BPP, BQP ), které zobecňují P v rámci PSPACE. Není známo, zda jsou některé z těchto omezení přísné.

v teorie složitosti, PP je třída rozhodovací problémy řešitelný a pravděpodobnostní Turingův stroj v polynomiální čas s pravděpodobností chyby menší než 1/2 pro všechny instance. Zkratka PP označuje pravděpodobnostní polynomiální čas. Byla definována třída složitosti^[1] Gill v roce 1977.

Pokud je problém s rozhodnutím PP, pak existuje algoritmus, který umožňuje otáčet mince a dělat náhodná rozhodnutí. Je zaručeno, že běží v polynomiálním čase. Pokud je odpověď ANO, algoritmus odpoví ANO s pravděpodobností větší než 1/2. Pokud je odpověď NE, algoritmus odpoví ANO s pravděpodobností menší nebo rovnou 1/2. Z praktičtějšího hlediska jde o třídu problémů, které lze vyřešit s jakoukoli pevnou mírou přesnosti spuštěním randomizovaného algoritmu polynomiálního času v dostatečném (ale omezeném) počtu opakování.

Turingovy stroje, které jsou polynomiálně vázané a pravděpodobnostní, jsou charakterizovány jako PPT, což je zkratka pro pravděpodobnostní polynomiální časové stroje.^[2] Tato charakterizace Turingových strojů nevyžaduje omezenou pravděpodobnost chyby. Proto, PP je třída složitosti obsahující všechny problémy řešitelné PPT strojem s pravděpodobností chyby menší než 1/2.

Alternativní charakterizace PP je soubor problémů, které lze vyřešit pomocí a nedeterministický Turingův stroj v polynomiálním čase, kdy podmínkou přijetí je, že většina (více než polovina) výpočetních cest přijímá. Z tohoto důvodu někteří autoři navrhli alternativní název Většina-P.^[3]

Definice

Jazyk L je v PP jen tehdy, pokud existuje pravděpodobnostní Turingův stroj M, takový, že

• M běží na polynomiálním čase na všech vstupech
• Pro všechny X v L, M výstupy 1 s pravděpodobností striktně větší než 1/2
• Pro všechny X ne v L, M výstupy 1 s pravděpodobností menší nebo rovnou 1/2.

Alternativně, PP lze definovat pouze pomocí deterministických Turingových strojů. Jazyk L je v PP právě když existuje polynom p a deterministický Turingův stroj M, takový, že

• M běží na polynomiálním čase na všech vstupech
• Pro všechny X v L, zlomek řetězců y délky p(|X|) které uspokojí M (x, y) = 1 je přísně větší než 1/2
• Pro všechny X ne v L, zlomek řetězců y délky p(|X|) které uspokojí M (x, y) = 1 je menší nebo rovno 1/2.

V obou definicích lze „menší než nebo rovný“ změnit na „menší než“ (viz níže) a prahovou hodnotu 1/2 lze nahradit jakýmkoli pevným racionálním číslem v (0,1), aniž by došlo ke změně třídy.

PP vs BPP

BPP je podmnožinou PP; lze to považovat za podmnožinu, pro kterou existují efektivní pravděpodobnostní algoritmy. Rozdíl je v pravděpodobnosti chyby, která je povolena: v BPP, algoritmus musí dát správnou odpověď (ANO nebo NE) s pravděpodobností překročení určité pevné konstanty c> 1/2, například 2/3 nebo 501/1000. Je-li tomu tak, pak můžeme spustit algoritmus několikrát a hlasovat většinou, abychom dosáhli jakékoli požadované pravděpodobnosti správnosti menší než 1, pomocí Černoff svázán. Tento počet opakování se zvyšuje, pokud C přiblíží se k 1, ale to nezávisí na velikosti vstupu n.

Důležité je, že tato konstanta C není dovoleno záviset na vstupu. Na druhou stranu a PP algoritmus smí provádět něco jako následující:

• V instanci ANO vydejte ANO s pravděpodobností 1/2 + 1/2ⁿ, kde n je délka vstupu.
• V případě NO výstup YES s pravděpodobností 1/2 - 1/2ⁿ.

Protože tyto dvě pravděpodobnosti jsou tak blízko u sebe, zejména u velkých n, i když jej spustíme mnohokrát, je velmi obtížné zjistit, zda pracujeme na instanci ANO nebo NE. Pokus o dosažení pevné požadované úrovně pravděpodobnosti pomocí většinového hlasování a Chernoffova vázaného vyžaduje řadu opakování, která jsou exponenciální v n.

PP ve srovnání s jinými třídami složitosti

PP obsahuje BPP, protože pravděpodobnostní algoritmy popsané v definici BPP tvoří podmnožinu těch v definici PP.

PP také obsahuje NP. Abychom to dokázali, ukážeme, že NP-kompletní uspokojivost problém patří PP. Zvažte pravděpodobnostní algoritmus, který vzhledem k danému vzorci F(X₁, X₂, ..., X_n) vybere úkol X₁, X₂, ..., X_n rovnoměrně náhodně. Potom algoritmus zkontroluje, zda přiřazení vytváří vzorec F skutečný. Pokud ano, vydá ANO. Jinak s pravděpodobností vydá ANO ${ displaystyle { frac {1} {2}} - { frac {1} {2 ^ {n + 1}}}}$ a NE s pravděpodobností ${ displaystyle { frac {1} {2}} + { frac {1} {2 ^ {n + 1}}}}$.

Pokud je vzorec neuspokojivý, bude algoritmus vždy vydávat ANO s pravděpodobností ${ displaystyle { frac {1} {2}} - { frac {1} {2 ^ {n + 1}}} <{ frac {1} {2}}}$. Pokud existuje uspokojivé přiřazení, vydá alespoň s pravděpodobností ANO${ displaystyle left ({ frac {1} {2}} - { frac {1} {2 ^ {n + 1}}} right) cdot left (1 - { frac {1} { 2 ^ {n}}} vpravo) +1 cdot { frac {1} {2 ^ {n}}} = { frac {1} {2}} + { frac {1} {2 ^ { 2n + 1}}}> { frac {1} {2}}}$(přesně 1/2, pokud vybralo neuspokojivé přiřazení a 1, pokud vybralo uspokojivé přiřazení, v průměru na nějaké číslo větší než 1/2). Tento algoritmus tedy zajišťuje uspokojivost PP. Tak jako SAT je NP-úplný a můžeme předponu před každou deterministickou polynomial-time many-one reduction na PP algoritmus, NP je obsažen v PP. Protože PP je uzavřen pod doplňkem, obsahuje také co-NP.

Dále PP obsahuje MA,^[4] který zahrnuje předchozí dvě inkluze.

PP také obsahuje BQP, třída rozhodovacích problémů řešitelná efektivním polynomiálním časem kvantové počítače. Ve skutečnosti je BQP nízký pro PP, což znamená, že a PP stroj nedosahuje žádné výhody z toho, že je schopen vyřešit BQP problémy okamžitě. Třída polynomiálního času na kvantových počítačích s dodatečný výběr, PostBQP, je rovný PP^[5] (vidět #PostBQP níže).

Dále PP obsahuje QMA, který zahrnuje inkluze MA a BQP.

Polynomiální Turingův stroj s PP věštec (P^PP) může vyřešit všechny problémy v PH, celá polynomiální hierarchie. Tento výsledek ukázal Seinosuke Toda v roce 1989 a je známá jako Todova věta. To svědčí o tom, jak těžké je problémy vyřešit PP. Třída #P je v jistém smyslu asi tak těžké, protože P^#P = P^PP a proto P^#P obsahuje PH také.

PP přísně obsahuje TC⁰, třída uniformy konstantní hloubky, neomezeného fanouška booleovské obvody s většinové brány. (Allender 1996, citovaný v Burtschick 1999).

PP je obsažen v PSPACE. To lze snadno ukázat vystavením algoritmu polynomiálního prostoru pro MAJSAT, definované níže; jednoduše vyzkoušejte všechny úkoly a spočítejte počet uspokojivých.

PP není obsažen v VELIKOST(č^k) pro libovolné k (důkaz ).

Kompletní problémy a další vlastnosti

Na rozdíl od BPP, PP je spíše syntaktická než sémantická třída. Jakýkoli pravděpodobnostní stroj v polynomiálním čase rozpozná nějaký jazyk PP. Naproti tomu, vzhledem k popisu pravděpodobnostního stroje s polynomiálním časem je obecně nerozhodnutelné určit, zda rozpoznává jazyk v BPP.

PP má přirozené úplné problémy, například MAJSAT. MAJSAT je rozhodovací problém, při kterém je dán booleovský vzorec F. Odpověď musí být ANO, pokud více než polovina všech úkolů X₁, X₂, ..., X_n aby F byla pravdivá a jinak NE.

Důkaz, že PP je uzavřen pod doplňkem

Nechat L být jazykem v PP. Nechat ${ displaystyle L ^ {c}}$ označit doplněk L. Podle definice PP existuje pravděpodobnostní algoritmus polynomiálního času A s majetkem, který

${ displaystyle x v L Rightarrow Pr [A { text {přijímá}} x]> { frac {1} {2}} quad { text {a}} quad x ne v L Rightarrow Pr [A { text {přijímá}} x] leq { frac {1} {2}}.}$

Tvrdíme to bez ztráty obecnosti „druhá nerovnost je vždy přísná; teorém lze odvodit z tohoto tvrzení: let ${ displaystyle A ^ {c}}$ označte stroj, který je stejný jako A kromě toho ${ displaystyle A ^ {c}}$ přijímá, když A odmítl a naopak. Pak

${ displaystyle x v L ^ {c} Rightarrow Pr [A ^ {c} { text {přijímá}} x]> { frac {1} {2}} quad { text {a}} quad x not v L ^ {c} Rightarrow Pr [A ^ {c} { text {přijímá}} x] <{ frac {1} {2}},}$

což z toho vyplývá ${ displaystyle L ^ {c}}$ je v PP.

Nyní to ospravedlňujeme, aniž bychom ztratili obecný předpoklad. Nechat ${ displaystyle f (| x |)}$ být horní mez polynomu na provozní době A na vstupu X. Tím pádem A dělá nanejvýš ${ displaystyle f (| x |)}$ náhodné převrácení mince během jejího provádění. Zejména je pravděpodobnost přijetí celočíselným násobkem ${ displaystyle 2 ^ {- f (| x |)}}$ a máme:

${ displaystyle x in L Rightarrow Pr [A { text {přijímá}} x] geq { frac {1} {2}} + { frac {1} {2 ^ {f (| x | )}}}.}$

Definujte stroj A′ Takto: na vstupu X, A′ Běží A jako podprogram a odmítne, pokud A odmítl; jinak, pokud A by přijal, APřevrátí ${ displaystyle f (| x |) +1}$ coiny a odmítne, jsou-li to všechny hlavy, a akceptuje jinak. Pak

${ displaystyle x not in L Rightarrow Pr [A '{ text {přijímá}} x] leq { frac {1} {2}} cdot left (1 - { frac {1} {2 ^ {f (| x |) +1}}} right) <{ frac {1} {2}} quad { text {and}} quad x in L Rightarrow Pr [A '{ text {přijímá}} x] geq left ({ frac {1} {2}} + { frac {1} {2 ^ {f (| x |)}}} right) cdot left (1 - { frac {1} {2 ^ {f (| x |) +1}}} right)> { frac {1} {2}}.}$

To ospravedlňuje předpoklad (od A′ Je stále pravděpodobnostní algoritmus polynomiálního času) a doplňuje důkaz.

David Russo prokázal v roce 1985 Ph.D. teze^[6] že PP je uzavřen pod symetrický rozdíl. Bylo to otevřený problém po dobu 14 let, zda PP byl uzavřen pod svaz a průsečík; toto urovnali kladně Beigel, Reingold a Spielman.^[7] Alternativní důkazy byly později poskytnuty Li^[8] a Aaronson (viz #PostBQP níže).

Jiné ekvivalentní třídy složitosti

PostBQP

Třída kvantové složitosti BQP je třída problémů řešitelných v polynomiální čas na kvantový Turingův stroj. Přidáváním dodatečný výběr, volala se větší třída PostBQP je získáno. Neformálně postselekce dává počítači následující sílu: kdykoli má nějaká událost (například měření qubitu v určitém stavu) nenulovou pravděpodobnost, můžete předpokládat, že k ní dojde.^[9] Scott Aaronson to v roce 2004 ukázal PostBQP je rovný PP.^[5][10] Tato formulace PP usnadňuje zobrazování určitých výsledků, například takových PP je uzavřen v průsečíku (a tedy pod sjednocením), že BQP je nízký pro PP, a to QMA je obsažen v PP.

PQP

PP se také rovná další třídě kvantové složitosti známé jako PQP, což je neomezený analog chyby BQP. Označuje třídu rozhodovacích problémů řešitelných kvantovým počítačem v polynomiálním čase s pravděpodobností chyby menší než 1/2 pro všechny instance. I když jsou použity všechny amplitudy PQP-výpočet je stále čerpán z algebraických čísel PQP se shoduje s PP.^[11]

Poznámky

Reference

• Papadimitriou, C. (1994). „kapitola 11“. Výpočetní složitost. Addison-Wesley..
• Allender, E. (1996). Msgstr "Poznámka o spodních mezích jednotného obvodu pro hierarchii počítání". Sborník 2. mezinárodní konference v oblasti výpočetní techniky a kombinatoriky (COCOON). Přednášky z informatiky. 1090. Springer-Verlag. str. 127–135..
• Burtschick, Hans-Jörg; Vollmer, Heribert (1999). „Kvantifikátory Lindström a definovatelnost Leaf Language“. ECCC  TR96-005. Citovat deník vyžaduje | deník = (Pomoc).

externí odkazy

• Složitost Zoo: PP