PP (kompleksitet) - PP (complexity)

PP i forhold til andre sannsynlighetskompleksitetsklasser ( ZPP , RP , co-RP, BPP , BQP ), som generaliserer P innen PSPACE . Det er ukjent om noen av disse inkluderingene er strenge.

I kompleksitetsteorien er PP klassen av beslutningsproblemer som kan løses av en sannsynlig Turing -maskin på polynomtid , med en sannsynlighet for feil på mindre enn 1/2 for alle tilfeller. Forkortelsen PP refererer til sannsynlig polynomtid. Kompleksitetsklassen ble definert av Gill i 1977.

Hvis et beslutningsproblem er i PP , så er det en algoritme for det som har lov til å snu mynter og ta tilfeldige beslutninger. Det vil garantert gå i polynomtid. Hvis svaret er JA, vil algoritmen svare JA med sannsynlighet mer enn 1/2. Hvis svaret er NEI, vil algoritmen svare JA med sannsynlighet mindre enn eller lik 1/2. I mer praktiske termer er det klassen av problemer som kan løses til en bestemt grad av nøyaktighet ved å kjøre en randomisert, polynomisk tidsalgoritme et tilstrekkelig (men begrenset) antall ganger.

Turningsmaskiner som er polynomt bundet og sannsynlighetsfulle karakteriseres som PPT , som står for sannsynlige polynom-tidsmaskiner. Denne karakteriseringen av Turing -maskiner krever ikke en begrenset feil sannsynlighet. Derfor er PP kompleksitetsklassen som inneholder alle problemer som kan løses av en PPT -maskin med en sannsynlighet for feil på mindre enn 1/2.

En alternativ karakterisering av PP er settet med problemer som kan løses av en ikke -deterministisk Turing -maskin i polynomtid der akseptbetingelsen er at et flertall (mer enn halvparten) av beregningsveier godtar. På grunn av dette har noen forfattere foreslått det alternative navnet Majority-P .

Definisjon

Et språk L er i PP hvis og bare hvis det finnes en sannsynlig Turing -maskin M , slik at

• M kjører i polynomtid på alle innganger
• For alle x i L , M utgang 1 med sannsynlighet strengt større enn 1/2
• For alle x som ikke er i L , M utganger 1 med sannsynlighet mindre enn eller lik 1/2.

Alternativt kan PP defineres ved hjelp av bare deterministiske Turing -maskiner. Et språk L er i PP hvis og bare hvis det eksisterer et polynom p og deterministisk Turing -maskin M , slik at

• M kjører i polynomtid på alle innganger
• For alle x i L er brøkdelen av strengene y med lengden p (| x |) som tilfredsstiller M (x, y) = 1 strengt større enn 1/2
• For alle x ikke i L er brøkdelen av strengene y med lengden p (| x |) som tilfredsstiller M (x, y) = 1 mindre enn eller lik 1/2.

I begge definisjonene kan "mindre enn eller lik" endres til "mindre enn" (se nedenfor), og terskelen 1/2 kan erstattes av et hvilket som helst fast rasjonelt tall i (0,1), uten å endre klassen.

PP vs BPP

BPP er en delmengde av PP ; det kan sees på som delsettet som det finnes effektive sannsynlighetsalgoritmer for. Skillet er i feil sannsynligheten som er tillatt: i BPP må en algoritme gi riktig svar (JA eller NEI) med sannsynlighet som overstiger noen fast konstant c> 1/2, for eksempel 2/3 eller 501/1000. Hvis dette er tilfellet, kan vi kjøre algoritmen flere ganger og ta et flertall for å oppnå ønsket sannsynlighet for korrekthet mindre enn 1 ved å bruke Chernoff -grensen . Dette antallet repetisjoner øker hvis c blir nærmere 1/2, men det avhenger ikke av inngangsstørrelsen n .

Det viktige er at denne konstante c ikke får lov til å avhenge av inngangen. På den annen side har en PP -algoritme lov til å gjøre noe som følgende:

• På en JA -forekomst, skriv ut JA med sannsynlighet 1/2 + 1/2 ⁿ , hvor n er lengden på inngangen.
• På et NO -forekomst, send ut JA med sannsynlighet 1/2 - 1/2 ⁿ .

Fordi disse to sannsynlighetene er så nær hverandre, spesielt for store n , selv om vi kjører det et stort antall ganger, er det veldig vanskelig å si om vi opererer på en JA -forekomst eller en NEI -forekomst. Forsøk på å oppnå et fast ønsket sannsynlighetsnivå ved bruk av flertallstemme og Chernoff -grensen krever en rekke repetisjoner som er eksponentiell i n .

PP sammenlignet med andre kompleksitetsklasser

PP inkluderer BPP , siden sannsynlighetsalgoritmer beskrevet i definisjonen av BPP danner en undersett av de i definisjonen av PP .

PP inkluderer også NP . For å bevise dette viser vi at NP-komplett tilfredsstillelsesproblem tilhører PP . Tenk på en sannsynlighetsalgoritme som gitt formelen F ( x ₁ ,  x ₂ , ...,  x _n ) velger en oppgave x ₁ ,  x ₂ , ...,  x _n jevnt tilfeldig. Deretter sjekker algoritmen om oppgaven gjør formelen F sann. Hvis ja, sender det ut JA. Ellers sender den JA ut med sannsynlighet og NEI med sannsynlighet . ${\ displaystyle {\ frac {1} {2}}-{\ frac {1} {2^{n+1}}}}$${\ displaystyle {\ frac {1} {2}}+{\ frac {1} {2^{n+1}}}}$

Hvis formelen ikke er tilfredsstillende, vil algoritmen alltid sende ut JA med sannsynlighet . Hvis det eksisterer en tilfredsstillende oppgave, vil den sende YES med sannsynlighet minst (nøyaktig 1/2 hvis den valgte en utilfredsstillende oppgave og 1 hvis den valgte en tilfredsstillende oppgave, i gjennomsnitt til et tall større enn 1/2). Dermed setter denne algoritmen tilfredshet i PP . Siden SAT er NP-komplett, og vi kan prefiks enhver deterministisk polynom-mange-en-reduksjon på PP- algoritmen, er NP inkludert i PP . Fordi PP er lukket under komplement, inkluderer det også co-NP . ${\ displaystyle {\ frac {1} {2}}-{\ frac {1} {2^{n+1}}} <{\ frac {1} {2}}}$${\ displaystyle \ left ({\ frac {1} {2}}-{\ frac {1} {2^{n+1}}} \ right) \ cdot \ left (1-{\ frac {1} { 2^{n}}} \ høyre) +1 \ cdot {\ frac {1} {2^{n}}} = {\ frac {1} {2}}+{\ frac {1} {2^{ 2n+1}}}> {\ frac {1} {2}}}$

Videre inkluderer PP MA , som underbygger de to foregående inkluderingene.

PP inkluderer også BQP , klassen av beslutningsproblemer som kan løses ved effektive polynomiske kvantemaskiner . Faktisk er BQP lav for PP , noe som betyr at en PP -maskin ikke oppnår noen fordel av å kunne løse BQP -problemer umiddelbart. Klassen av polynomtid på kvantemaskiner med postvalg , PostBQP , er lik PP (se #PostBQP nedenfor).

Videre inkluderer PP QMA , som innebærer inkludering av MA og BQP .

En polynomisk Turing -maskin med et PP -orakel ( P ^PP ) kan løse alle problemer i PH , hele det polynomiske hierarkiet . Dette resultatet ble vist av Seinosuke Toda i 1989 og er kjent som Todas teorem . Dette er bevis på hvor vanskelig det er å løse problemer i PP . Klassen #P er på en måte omtrent like hard, siden P ^#P = P ^PP og derfor P ^{#P også} inkluderer PH .

PP inkluderer strengt TC ⁰ , klassen med konstant-dybde, unbounded-fan-in uniform boolske kretser med majoritetsporter . (Allender 1996, som sitert i Burtschick 1999).

PP er inkludert i PSPACE . Dette kan enkelt vises ved å vise en polynom-rom-algoritme for MAJSAT , definert nedenfor; bare prøv alle oppgavene og tell antall tilfredsstillende.

PP er ikke inkludert i SIZE (n ^k ) for k ( bevis ).

Komplette problemer og andre eiendommer

I motsetning til BPP er PP en syntaktisk, snarere enn semantisk klasse. Enhver polynom-tid-probabilistisk maskin gjenkjenner noe språk i PP . I kontrast, gitt en beskrivelse av en polynom-tidssannsynlighetsmaskin, er det generelt uavgjort om det gjenkjenner et språk i BPP .

PP har naturlige komplette problemer, for eksempel MAJSAT . MAJSAT er et beslutningsproblem der man får en boolsk formel F. Svaret må være JA hvis mer enn halvparten av alle oppgavene x ₁ ,  x ₂ , ...,  x _n gjør F sant og NEI ellers.

Bevis på at PP er lukket under komplement

La L være et språk i PP . La betegne komplement av L . Ved definisjonen av PP er det en polynom-tid probabilistisk algoritme A med egenskapen som ${\ displaystyle L^{c}}$

${\ displaystyle x \ in L \ Rightarrow \ Pr [A {\ text {accept}} x]> {\ frac {1} {2}} \ quad {\ text {og}} \ quad x \ not \ in L \ Rightarrow \ Pr [A {\ tekst {godtar}} x] \ leq {\ frac {1} {2}}.}$

Vi hevder at uten tap av generalitet er sistnevnte ulikhet alltid streng; teoremet kan utledes av denne påstanden: la oss betegne maskinen som er den samme som A bortsett fra at den godtar når A ville avvise, og omvendt. Deretter ${\ displaystyle A^{c}}$${\ displaystyle A^{c}}$

${\ displaystyle x \ i L^{c} \ Rightarrow \ Pr [A^{c} {\ text {aksepterer}} x]> {\ frac {1} {2}} \ quad {\ text {og}} \ quad x \ not \ in L^{c} \ Rightarrow \ Pr [A^{c} {\ text {accept}} x] <{\ frac {1} {2}},}$

noe som betyr at det er i PP . ${\ displaystyle L^{c}}$

Nå begrunner vi vår antagelse uten tap av generalitet. La oss være den polynomiske øvre grensen for kjøretiden til A på inngang x . Dermed gjør A høyst tilfeldige myntsvingninger under utførelsen. Spesielt er sannsynligheten for aksept et heltall multiplum av og vi har: ${\ displaystyle f (| x |)}$${\ displaystyle f (| x |)}$${\ displaystyle 2^{-f (| x |)}}$

${\ displaystyle x \ i L \ Rightarrow \ Pr [A {\ text {aksepterer}} x] \ geq {\ frac {1} {2}}+{\ frac {1} {2^{f (| x | )}}}}.}$

Definere en maskin A 'som følger: på inngangs x , A ' løper A som en subrutine, og vrak hvis A ville avvise; ellers, hvis A godtar, vender A ′ mynter og avviser om de alle er hoder, og godtar annet. Deretter ${\ displaystyle f (| x |) +1}$

${\ displaystyle x \ not \ in L \ Rightarrow \ Pr [A '{\ text {accept}} x] \ leq {\ frac {1} {2}} \ cdot \ left (1-{\ frac {1} {2^{f (| x |) +1}}} \ høyre) <{\ frac {1} {2}} \ quad {\ text {og}} \ quad x \ i L \ Rightarrow \ Pr [A '{\ tekst {godtar}} x] \ geq \ venstre ({\ frac {1} {2}}+{\ frac {1} {2^{f (| x |)}}} \ høyre) \ cdot \ venstre (1-{\ frac {1} {2^{f (| x |) +1}}} \ høyre)> {\ frac {1} {2}}.}$

Dette begrunner antagelsen (siden A ′ fortsatt er en polynom-tid-sannsynlig algoritme) og fullfører beviset.

David Russo beviste i sin doktorgrad i 1985. tese om at PP lukkes under symmetrisk forskjell . Det var et åpent problem i 14 år om PP ble stengt under fagforening og kryss ; dette ble avgjort bekreftende av Beigel, Reingold og Spielman. Alternative bevis ble senere gitt av Li og Aaronson (se #PostBQP nedenfor).

Andre tilsvarende kompleksitetsklasser

PostBQP

Kvante kompleksitet klassen BQP er klassen av problemer løsbar i polynomisk tid på en kvante Turing maskin . Ved å legge til postvalg , oppnås en større klasse kalt PostBQP . Uformelt gir postvalg datamaskinen følgende kraft: Når en hendelse (for eksempel å måle en qubit i en bestemt tilstand) har sannsynlighet uten null, har du lov til å anta at den finner sted. Scott Aaronson viste i 2004 at PostBQP er lik PP . Denne omformuleringen av PP gjør det lettere å vise visse resultater, for eksempel at PP er stengt under kryss (og dermed under union), at BQP er lav for PP , og at QMA er inkludert i PP .

PQP

PP er også lik en annen kvantekompleksitetsklasse kjent som PQP , som er den ubegrensede feilanalogen til BQP . Den angir klassen av beslutningsproblemer som kan løses av en kvantemaskin i polynomtid, med en sannsynlighet for feil på mindre enn 1/2 for alle forekomster. Selv om alle amplituder som brukes til PQP -beregning er hentet fra algebraiske tall, er PQP fortsatt sammenfallende med PP .

Merknader

Referanser

• Papadimitriou, C. (1994). "kapittel 11". Beregningskompleksitet . Addison-Wesley..
• Allender, E. (1996). "En merknad om enhetlige krets nedre grenser for tellehierarkiet". Proceedings 2nd International Computing and Combinatorics Conference (COCOON) . Forelesningsnotater i informatikk. 1090 . Springer-Verlag. s. 127–135..
• Burtschick, Hans-Jörg; Vollmer, Heribert (1999). "Lindström Quantifiers and Leaf Language Definability". ECCC  TR96-005 . Cite journal krever |journal=( hjelp ).

Eksterne linker

• Kompleks Zoo : PP