Clasa BPP

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 10 august 2021; verificările necesită 2 modificări .

În teoria algoritmilor , clasa de complexitate BPP (din engleza bounded-error, probabilistic, polynomial ) este clasa predicatelor , rapid (în timp polinomial) calculabile și oferind un răspuns cu mare probabilitate (mai mult, sacrificând timpul, poți atinge o precizie arbitrar de mare a răspunsului). Problemele rezolvate prin metode probabilistice și situate în BPP apar foarte des în practică.

Definiție formală

Clasa BPP este clasa de predicate P(x) care sunt calculabile pe mașini Turing probabilistice (mașini Turing obișnuite cu o bandă de numere aleatoare) în timp polinomial cu o eroare de cel mult ⅓. Aceasta înseamnă că mașina probabilistică Turing care calculează valoarea predicatului va da un răspuns în timp egal cu O(n k ) , unde n este lungimea lui x , iar dacă răspunsul corect este 1, atunci mașina produce 1 cu o probabilitate de cel puțin ⅔ și invers. Mulțimea de cuvinte pe care P(x) returnează 1 se numește limbaj recunoscut de predicatul P(x) .

Numărul ⅓ din definiție este ales în mod arbitrar: dacă în locul lui alegem orice număr p care este strict mai mic decât ½, atunci obținem aceeași clasă. Acest lucru este adevărat deoarece dacă există o mașină Turing care recunoaște un limbaj cu o probabilitate de eroare p în timp O(n k ) , atunci precizia poate fi îmbunătățită în mod arbitrar cu o creștere relativ mică în timp. Dacă rulăm mașina de n ori la rând și luăm rezultatul celor mai multe rulări ca rezultat, atunci probabilitatea de eroare scade la , iar timpul devine O(n k+1 ) . Aici, n rulări ale mașinii sunt tratate ca o schemă Bernoulli cu n încercări și o probabilitate de succes de 1-p , iar formula erorii este probabilitatea de eșec cel puțin jumătate din timp. Dacă rulăm acum mașina n de 2 ori la rând, atunci timpul va crește la O(n k+2 ) , iar probabilitatea de eroare va scădea la . Astfel, pe măsură ce exponentul polinomului de estimare a timpului crește, precizia crește exponențial și orice valoare dorită poate fi atinsă. $\left(2{\sqrt {p(1-p)}}\right)^{n}$ $\left(2{\sqrt {p(1-p)}}\right)^{{n^{2}}}$

Algoritmi Monte Carlo

Un algoritm probabilistic adoptă un limbaj conform standardului Monte Carlo dacă probabilitatea de eroare a algoritmului nu depășește . Adică , unde este predicatul că cuvântul aparține limbii . Astfel, clasa BPP este formată din predicate astfel încât pentru ei există un algoritm probabilistic polinomial care preia limbajul lor conform standardului Monte Carlo. Astfel de algoritmi sunt numiți și algoritmi Monte Carlo. ${\mathcal {A}}$ $L$ $1/3$ $\mathbb {P} ({\mathcal {A}}(x)=P(x))\geq 2/3$ $P(x)$ $X$ $L$

Relația cu algoritmii din Las Vegas

Fie algoritmul Monte Carlo cu complexitate de timp , unde este lungimea de intrare. De asemenea, luăm ca limită inferioară probabilitatea ca algoritmul Las Vegas să dea rezultatul corect și ca un algoritm cu complexitate de timp , care verifică rezultatul pentru fiabilitate. Într-un astfel de caz, există un algoritm cu complexitatea timpului așteptat . Pentru a-l demonstra, imaginați-vă ce cauzează și până când acesta confirmă corectitudinea rezultatului. Atunci timpul de rulare a unei iterații a unei astfel de proceduri va fi . Probabilitatea ca iterațiile să fie repetate este , ceea ce înseamnă că numărul așteptat de iterații este , pe baza faptului că . ${\mathcal {B}}$ $f(n)$ $p(n)$ $\mathcal{A}$ ${\mathcal {C}}$ $g(n)$ $\mathcal{A}$ $\mathcal{A}$ $(f(n)+g(n))/p(n)$ $\mathcal{A}$ ${\mathcal {B}}$ ${\mathcal {C}}$ ${\mathcal {C}}$ $f(n)+g(n)$ $k$ $(1-p(n))^{k-1}\cdot p(n)$ $\sum _{k=1}^{\infty }k\cdot (1-p(n))^{k-1}\cdot p(n)=1/p(n)$ $\sum _{k=1}^{\infty}k\cdot x^{k}=x/(1-x)^{2)$

Relații cu alte clase

BPP în sine este închis sub complement. Clasa P este inclusă în BPP deoarece oferă un răspuns în timp polinomial cu eroare zero. BPP este inclus în clasa ierarhiei polinomiale și, ca urmare, este inclus în PH și PSPACE . De asemenea, se știe că include BPP în clasa P/Poly . $\Sigma _{2}^{p}\cap \Pi _{2}^{p}$

Omologul cuantic al clasei BPP (cu alte cuvinte, o extensie a clasei BPP la calculatoarele cuantice ) este clasa BQP .

{\mbox{BPP}}\subseteq {\mbox{BQP}}

Alte proprietăți

Până în 2002, una dintre cele mai cunoscute probleme din clasa BPP a fost problema de recunoaștere a numerelor prime , pentru care existau mai mulți algoritmi probabilistici polinomiali diferiți, cum ar fi testul Miller-Rabin , dar niciunul determinist. Totuși, în 2002, matematicienii indieni Agrawal, Kayan și Saxena au găsit un algoritm polinom determinist , care au demonstrat astfel că problema recunoașterii unui număr prim se află în clasa P . Algoritmul lor AKS propus (numit după primele litere ale numelui lor de familie) recunoaște caracterul prim al unui număr de lungime n în timp O(n 4 ) .

Clasele de complexitate ale algoritmilor
Considerată ușoară	DLOGTIME AC 0 ACC 0 TC0 [ en L SL RL NL NC SC CC P P-complet ZPP RP BPP BQP EQP APX
Ar trebui să fie dificil	U.P. NP NP complet co-NP co-NP-complet AM M.A._ QMA PH ⊕P PP #P #P IP PSPACE PSPACE-complete
Considerat dificil	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTAR R PR RE RE-completare Co-RE Co-RE-complete TOATE