BPP (complexitate)

În teoria complexității computaționale , BPP (mărginite-eroare de timp probabilist polinom „timp polinomial probabilist cu eroare limitată“) este o clasă de complexitate la care aceste probleme de decizie care necesită un timp polinomial pentru a avea o soluție probabilistic corectă este locul. Mai precis, acestea pot fi rezolvate în timp polinomial de o mașină Turing probabilistic , cu o probabilitate de eroare de cel mult 1/3 , pentru toate cazurile.

BPP algoritm (1 execuție)
	Răspuns produs
Răspuns corect	DA	NU
DA	≥ 2/3	≤ 1/3
NU	≤ 1/3	≥ 2/3
BPP algoritm (k execuții)
	Răspuns produs
Răspuns corect	DA	NU
DA	> 1 - 2 ^{- ck}	<2 ^{- ck}
NU	<2 ^{- ck}	> 1 - 2 ^{- ck}
pentru unele constanta c> 0

Informal, o problemă este în BPP dacă există un algoritm pentru ea, care are următoarele proprietăți:

Este permis să arunce monede și de a lua decizii aleatorii
Este garantat că se efectuează în timp polinomial
În orice execuție a algoritmului dat, are o probabilitate de cel mult 1/3 din a da un răspuns greșit, dacă răspunsul este DA sau NU.

Introducere

BPP este una dintre cele mai mari clase „practice“ de probleme, adică cele mai multe dintre problemele de interes în BPP au eficient algoritmi probabilistici , care pot fi rulate pe mașini moderne reale. Din acest motiv, este de mare interes practic pe care problemele și clase de probleme sunt în cadrul BPP. BPP conține , de asemenea , P , clasa de probleme rezolvabile polinomului timp cu o mașină determinist, deoarece o mașină deterministă este un caz special al unei mașini probabilistic.

În practică, o probabilitate de eroare de 1/3 nu poate fi acceptabilă, cu toate acestea, alegerea 1/3 din definiția este arbitrară. Acesta poate fi orice constantă între 0 și 1/2 (exclusiv) și setul BPP va fi neschimbat. Nici măcar nu trebuie să fie constantă: aceeași clasă de probleme este definită prin permiterea unei erori mari de până la 1/2 - n ^{- c} pe de o parte, sau prin solicitarea unei erori mici de până la 2 ^{- n ^c} pe de altă parte , unde c este orice constantă pozitivă, iar n este lungimea de intrare. Ideea este că există o probabilitate de eroare, dar în cazul în care algoritmul este executat de multe ori, șansa ca cele mai multe execuții sunt greșite picături exponențial ca urmare a constrângerii Chernoff . ^[1] Acest lucru face posibil pentru a crea un algoritm extrem de precis , pur și simplu prin rularea algoritmului de mai multe ori și a lua un „vot majoritar“ , a răspunsurilor. De exemplu, dacă am definit clasa cu restricția că algoritmul ar putea fi greșit cu o probabilitate de cel mult 1/2 ^100, acest lucru ar da naștere la aceeași clasă de probleme.

Definiție

Un limbaj L este în BPP dacă și numai dacă există o probabilistic mașină Turing M, astfel încât

M lucrează pentru un timp polinomial la toate intrările
Pentru toate x în L, M emite 1 cu o mai mare probabilitate mare sau egală cu 2/3
Pentru toate x nu este în L, problemele M 1 cu probabilitate mai mică sau egală cu 1/3

Spre deosebire de ZPP clasa de complexitate, mașină M este necesar pentru a rula un timp polinomial la toate intrările, indiferent de rezultatul monede aleatoare răstoarnă.

Alternativ, BPP poate fi definit folosind mașini Turing numai deterministe. Un limbaj L este în BPP dacă și numai dacă există un timp p polinomial și o determinist mașină Turing M, astfel încât

M lucrează pentru un timp polinomial la toate intrările
Pentru toate x în L, fracția șirurilor y de lungime p (| x |) satisface M (x, y) = 1 este mai mare sau egal cu 2/3
Pentru toate x lui nu în L, fracțiunea șirurilor y de lungime p (| x |) satisface M (x, y) = 1 este mai mic sau egal cu 1/3

În această definiție, șirul y corespunde rezultatului monedei aleatoare basculează că mașina Turing probabilistă ar fi făcut. Pentru unele aplicații această definiție este de preferat, deoarece nu menționează mașinile Turing probabilistice.

Probleme

Pe lângă problemele din P, care sunt în mod evident în BPP, multe probleme au fost cunoscute, care erau în BPP, dar nu și în P. Numărul acestor probleme este în scădere, și este presupus că P = BPP.

Pentru o lungă perioadă de timp, una dintre cele mai mari probleme celebre , care a fost cunoscut a fi în BPP , dar să nu fie în poziția P a fost problema de a stabili dacă un anumit număr este prim . Cu toate acestea, în 2002 de hârtie PRIMES este în P , Manindra Agrawal si elevii ei Neeraj Kayal și Nitin Saxena a găsit un algoritm determinist în timp polinomial pentru această problemă, dovedind astfel că este în P.

Un exemplu important al unei probleme în BPP ( de fapt , în co-RP ) , care nu se cunoaște încă în P este verificarea identității polinoamelor , problema de a stabili dacă un polinom este identic egal cu polinomul zero. Cu alte cuvinte, există o sarcină variabilă, astfel încât, atunci când se calculează polinomul rezultatul este nenul? Este suficient să se aleagă valoarea fiecărei variabile în mod uniform la întâmplare , dintr - un subset finit de la valori mai mici d pentru a obține o probabilitate de eroare constrânsă, unde d este gradul total al polinomului. ^[2]

clase înrudite

Dacă eliminăm accesul la aleator din definiția BPP, obținem clasa de complexitate P. In definiția de clasă, dacă înlocuim comună mașina Turing cu un computer cuantic , vom obține BQP clasa.

Adăugarea postselection la BPP, sau permițând căi de calcul pentru a avea lungimi diferite, dă clasa BPP _cale. ^[3] _calea BPP este cunoscută pentru a conține NP și este conținută în omologul său cuantic PostBQP .

Un Monte Carlo algoritm este un algoritm randomizat , care este probabil să fie corecte. Probleme în clasa BPP au algoritmi Monte Carlo cu timpul de execuție polinomial constrânsă. Acest lucru se compara cu un Las Vegas algoritm , care este un algoritm randomizat , care ieșirile răspunsul corect, sau probleme cu „eșec“ , cu probabilitate redusă. Algoritmi Las Vegas cu runtimes constrânși de polinoame sunt folosite pentru a defini ZPP clasei. În mod alternativ, ZPP conține algoritmi probabilistici, care sunt întotdeauna corecte și au un timp de funcționare de așteptat polinomial. Acest lucru este mai slabă decât a spune că este un algoritm în timp polinomial, deoarece poate rula pentru timp polinomial, dar cu probabilitate foarte mică.

Proprietățile teoriei complexității

BPP în raport cu alte clase de complexitate probabilistice

BPP este cunoscut a fi închise în cadrul complement ; adică, BPP = co-BPP. BPP este scăzut de la sine, ceea ce înseamnă că o mașină BPP cu puterea de a rezolva problemele instantaneu BPP (un BPP mașină Oracle ) nu este mai puternic decât aparatul fără această putere suplimentară. În simboluri, BPP ^BPP = BPP.

Relația dintre BPP și NP este necunoscut: nu se știe dacă BPP este un subset al NP, NP este un subset al BPP sau în cazul în care sunt incomparabil. Dacă NP este conținută în BPP, care este considerată puțin probabilă , deoarece aceasta ar presupune soluții practice pentru NP-complete de probleme, NP = RP si PH ⊆ BPP. ^[4]

Este cunoscut faptul că RP este un subset al BPP, iar BPP este un subset al PP . Nu se cunoaște dacă aceste două sunt două subseturi strânse, din moment ce nici măcar nu știu dacă P este un subset strans de PSPACE. BPP este conținut în al doilea nivel al ierarhiei polinom și , prin urmare , este conținută în PH. Mai precis, Sipser-Lautemann teorema afirmă că $\ BPP\subseteq \Sigma _{2}\cap \Pi _{2}$ ${\ Displaystyle \ BPP \ subseteq \ Sigma _ {2} \ cap \ Pi _ {2}}$ $\ BPP \ subseteq \ Sigma _ {2} \ cap \ Pi _ {2}$ . Ca rezultat, P = NP conduce la P = BPP deoarece surpări PH la P în acest caz. Deci, fie P = BPP sau P ≠ NP sau ambele.

Teorema lui Adleman afirmă că aderarea în orice limbă în BPP poate fi determinată de o familie de polinoame de dimensiuni circuite Boolean , ceea ce înseamnă că BPP este conținută în P / poli . ^[5] Într - adevăr, ca o consecință a dovedi acest fapt, orice BPP algoritm de operare de pe intrările lungime constrânse pot fi derandomized într - un algoritm determinist care utilizează un șir fix de biți aleatorii. Găsirea acest șir poate fi costisitoare, cu toate acestea.

În ceea ce privește oracole, știm că există oracole A și B, astfel încât P ^A = BPP ^A și P ^B ≠ BPP ^B. Mai mult decât atât, în ceea ce privește oracolul aleatoare cu probabilitatea 1, P = BPP și BPP este strict conținută în NP și co-NP. ^[6]

Derandomization

Existența unor puternice generatoare de numere aleatoare este intuite de cei mai mulți experți în domeniu. Această presupunere implică faptul ca intamplarea nu dă putere de calcul suplimentar de calcul în timp polinomial, adică, P = RP = BPP. Rețineți că generatoarele comune nu sunt suficiente pentru a demonstra acest rezultat; orice algoritm probabilist implementat care utilizează un generator de numere aleatorii tipic va produce întotdeauna rezultate incorecte cu privire la anumite intrări, indiferent de semințe (deși aceste intrări pot fi rare).

László Babai , Lance Fortnow , Noam Nisan și Avi Wigderson a arătat că , dacă EXPTIME se prăbușește la MA , BPP este conținută în ^[7]

\mathbf {i.o.-SUBEXP} =\bigcap \nolimits _{\varepsilon >0}\mathbf {i.o.-DTIME} \left(2^{n^{\varepsilon }}\right).

{\ Displaystyle \ mathbf {io-SUBEXP} = \ bigcap \ NoLimits _ {\ varepsilon> 0} \ mathbf {io-DTIME} \ stânga (2 ^ {n ^ {\ varepsilon}} \ dreapta).}

{\ Mathbf {io-SUBEXP}} = \ bigcap \ NoLimits _ {{\ varepsilon> 0}} {\ mathbf {io-DTIME}} \ stânga (2 ^ {{n ^ {\ varepsilon}}} \ dreapta) .

Clasa I-SUBEXP, care vine de la SUBEXP infinit De multe ori, care este infinit de multe ori SUBEXP, conține problemele pe care algoritmi subesponenziale timp pentru infinit mai multe dimensiuni de intrare. De asemenea , au aratat ca P = BPP dacă ierarhia exponențială de timp, care este definit în termenii ierarhiei polinomului și că E ca E ^PH, se prăbușește la E; Cu toate acestea, rețineți că este presupus că ierarhia exponențială de timp nu de obicei colaps.

Russell Impagliazzo și Avi Wigderson a demonstrat că , dacă nici o problemă în E , în cazul în care

\mathbf {E} =\mathbf {DTIME} \left(2^{O(n)}\right),

{\ Displaystyle \ mathbf {E} = \ mathbf {DTIME} \ stânga (2 ^ {O (n)} \ dreapta)}

{\ Mathbf {E}} = {\ mathbf {DTIME}} \ stânga (2 ^ {{O (n)}} \ dreapta),

are circuit de complexitate 2 ^{Ω (n)} , atunci P = BPP. ^[8]

Notă

^ http://www.cs.sfu.ca/~kabanets/cmpt710/lec16.pdf
^ Sudan Madhu și Shien Jin Ong, Advanced Teoria Complexitate: Curs 6: Algoritmi studiu randomizat, Proprietăți de BPP , Massachusetts Institute of Technology: 6.841 / 18.405J, 26 februarie 2003.
^ [1] Data arhivării 05 august 2012 la Internet Archive .
^ Computațională Complexitate: trăgând în afară de cuanticitate , la weblog.fortnow.com. Adus de 06 martie 2014 (arhivate din original la 14 martie, 2006).
^ Adleman, LM , două teoreme la timp polinomial aleator, Proceedings al XIX -lea Simpozion anual IEEE cu privire la fundații de calcul, 1978, pp. 75-83.
^ Charles H. Bennett și John Gill, în raport cu un Aleator Oracle A, P ^ A! = NP ^ A! = Co-NP ^ A cu probabilitatea 1, în SIAM Journal Computing, vol. 10, nr. 1, 1981, pp. 96-113, ISSN 1,095-7,111 ( WC ACNP ).
^ László Babai, Lance Fortnow, Noam Nisan și Avi Wigderson (1993). „BPP are simulări în timp subexponential excepția cazului în care EXPTIME are dovezi publishabke“. Complexitatea computațională, 3: 307-318.
^ Russell Impagliazzo și Avi Wigderson (1997). "P = BPP dacă e nevoie de circuite exponențiale: Derandomizing XOR Lema". Lucrările celui de-al IX - lea Simpozion Anual ACM privind Teoria Computing, pp. 220-229. DOI : 10.1145 / 258533.258590

Bibliografie

Valentine Kabanets (2003). "CMPT 710 - Teoria Complexitate: Curs 16". Universitatea Simon Fraser .
Christos Papadimitriou , computațională Complexitate, prima ediție, Addison Wesley, 1993, ISBN 0-201-53082-1 . pp. 257-259 din secțiunea 11.3: „Surse aleatoare“. pp. 269-271 din secțiunea 11.4: "complexitate Circuit".
Michael Sipser , Introducere în teoria Computation, PWS Publishing, 1997, ISBN 0-534-94728-X . Secțiunea 10.2.1: "Clasa BPP, pp 336-339.".

linkuri externe

(RO) Princeton CS 597E: lista de hârtie Derandomization , pe cs.princeton.edu.
(RO) Harvard CS 225: Pseudorandomness pe courses.fas.harvard.edu. Adus de 06 martie 2014 (arhivate de original pe 05 august 2003).

Portal IT

Portalul de matematică

[1] ttp://www.cs.sfu.ca/~kabanets/cmpt710/lec16.pdf

[2] Sudan Madhu și Shien Jin Ong, Advanced Teoria Complexitate: Curs 6: Algoritmi studiu randomizat, Proprietăți de BPP , Massachusetts Institute of Technology: 6.841 / 18.405J, 26 februarie 2003.

[3] [1] Data arhivării 05 august 2012 la Internet Archive .

[4] Computațională Complexitate: trăgând în afară de cuanticitate , la weblog.fortnow.com. Adus de 06 martie 2014 (arhivate din original la 14 martie, 2006).

[5] Adleman, LM , două teoreme la timp polinomial aleator, Proceedings al XIX -lea Simpozion anual IEEE cu privire la fundații de calcul, 1978, pp. 75-83.

[6] Charles H. Bennett și John Gill, în raport cu un Aleator Oracle A, P ^ A! = NP ^ A! = Co-NP ^ A cu probabilitatea 1, în SIAM Journal Computing, vol. 10, nr. 1, 1981, pp. 96-113, ISSN 1,095-7,111 ( WC ACNP ).

[Babai-7] László Babai, Lance Fortnow, Noam Nisan și Avi Wigderson (1993). „BPP are simulări în timp subexponential excepția cazului în care EXPTIME are dovezi publishabke“. Complexitatea computațională, 3: 307-318.

[8] Russell Impagliazzo și Avi Wigderson (1997). "P = BPP dacă e nevoie de circuite exponențiale: Derandomizing XOR Lema". Lucrările celui de-al IX - lea Simpozion Anual ACM privind Teoria Computing, pp. 220-229. DOI : 10.1145 / 258533.258590

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]