Třída BPP

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 10. srpna 2021; kontroly vyžadují 2 úpravy .

V teorii algoritmů je třída složitosti BPP (z anglického bounded-error, probabilistic, polynomial ) třída predikátů , rychle (v polynomiálním čase) vyčíslitelné a poskytující odpověď s vysokou pravděpodobností (navíc obětovat čas, můžete dosáhnout libovolně vysoké přesnosti odpovědi). Problémy řešené pravděpodobnostními metodami a ležící v BPP se v praxi objevují velmi často.

Formální definice

Třída BPP je třída predikátů P(x) , které jsou vyčíslitelné na pravděpodobnostních Turingových strojích (běžné Turingovy stroje s páskou náhodných čísel) v polynomiálním čase s chybou ne větší než ⅓. To znamená, že pravděpodobnostní Turingův stroj, který počítá hodnotu predikátu, dá odpověď v čase rovném O(n k ) , kde n je délka x , a pokud je správná odpověď 1, pak stroj vytvoří 1 s pravděpodobnost alespoň ⅔ a naopak. Množina slov, pro kterou P(x) vrací 1, se nazývá jazyk rozpoznávaný predikátem P(x) .

Číslo ⅓ v definici je zvoleno libovolně: pokud místo něj zvolíme libovolné číslo p , které je striktně menší než ½, dostaneme stejnou třídu. To je pravda, protože pokud existuje Turingův stroj, který rozpozná jazyk s pravděpodobností chyby p v čase O(n k ) , pak lze přesnost libovolně dobře zlepšit s relativně malým nárůstem času. Pokud spustíme stroj nkrát za sebou a jako výsledek vezmeme výsledek většiny běhů, pak pravděpodobnost chyby klesne na , a čas se stane O(n k+1 ) . Zde je n běhů stroje považováno za Bernoulliho schéma s n pokusy a pravděpodobností úspěchu 1-p a chybový vzorec je pravděpodobnost selhání alespoň polovičního času. Pokud nyní spustíme stroj n 2krát za sebou, pak se čas zvýší na O(n k+2 ) a pravděpodobnost chyby klesne na . Jak se tedy zvyšuje exponent polynomu odhadujícího čas, přesnost roste exponenciálně a lze dosáhnout jakékoli požadované hodnoty. $\left(2{\sqrt {p(1-p)}}\right)^{n}$ $\left(2{\sqrt {p(1-p)}}\right)^{{n^{2}}}$

Algoritmy Monte Carlo

Pravděpodobnostní algoritmus převezme jazyk podle standardu Monte Carlo, pokud pravděpodobnost chyby algoritmu nepřekročí . To znamená, , kde je predikát, že slovo patří k jazyku . Třída BPP je tedy tvořena predikáty tak, že pro ně existuje polynomiální pravděpodobnostní algoritmus, který přebírá jejich jazyk podle standardu Monte Carlo. Takové algoritmy se také nazývají algoritmy Monte Carlo. ${\mathcal {A}}$ $L$ $1/3$ $\mathbb {P} ({\mathcal {A}}(x)=P(x))\geq 2/3$ $P(x)$ $X$ $L$

Vztah s algoritmy Las Vegas

Nechť algoritmus Monte Carlo s časovou složitostí , kde je vstupní délka. Také bereme jako spodní hranici pravděpodobnost, že algoritmus Las Vegas poskytne správný výsledek, a jako algoritmus s časovou složitostí , který kontroluje spolehlivost výsledku . V takovém případě existuje algoritmus s očekávanou časovou složitostí . Abyste to dokázali, představte si, co způsobuje a dokud to nepotvrdí správnost výsledku. Pak bude doba běhu jedné iterace takového postupu . Pravděpodobnost, že se iterace budou opakovat, je , což znamená, že očekávaný počet iterací je na základě skutečnosti, že . ${\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}$

Vztahy s jinými třídami

Samotný BPP je uzavřen pod doplňkem. Třída P je součástí BPP, protože dává odpověď v polynomiálním čase s nulovou chybou. BPP je zahrnut do třídy polynomiální hierarchie a v důsledku toho je zahrnut do PH a PSPACE . Je také známo, že zahrnuje BPP do třídy P/Poly . $\Sigma _{2}^{p}\cap \Pi _{2}^{p}$

Kvantovým protějškem třídy BPP (jinými slovy rozšíření třídy BPP na kvantové počítače ) je třída BQP .

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

Další vlastnosti

Až do roku 2002 byl jedním z nejznámějších problémů ve třídě BPP problém rozpoznávání prvočísel , pro který existovalo několik různých polynomických pravděpodobnostních algoritmů, jako je Miller-Rabinův test , ale žádný deterministický. V roce 2002 však indičtí matematici Agrawal, Kayan a Saxena našli deterministický polynomiální algoritmus , kteří tak dokázali, že problém rozpoznání prvočísla spočívá ve třídě P . Jejich navrhovaný algoritmus AKS (pojmenovaný podle prvních písmen jejich příjmení) rozpoznává prvočíslo čísla délky n v čase O(n 4 ) .

Třídy složitosti algoritmů
Považováno za světlo	DLOGTIME AC 0 ACC 0 TC0 [ en L SL RL NL NC SC CC P P-kompletní ZPP RP BPP BQP EQP APX
Prý to bude těžké	U.P. NP NP kompletní co-NP co-NP-kompletní AM M.A. QMA PH ⊕P PP #P #P- IP PSPACE PSPACE-complete
Považováno za obtížné	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY R PR RE RE-complete Co-RE Co-RE-complete VŠECHNY