BPP klasse

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 10. august 2021; checks kræver 2 redigeringer .

I teorien om algoritmer er kompleksitetsklassen BPP (fra engelsk bounded-error, probabilistic, polynomial ) klassen af prædikater , der hurtigt (i polynomiel tid) kan beregnes og giver et svar med høj sandsynlighed (udover at ofre tid, kan du opnå en vilkårlig høj nøjagtighed af svaret). Problemer løst ved sandsynlighedsmetoder og løgn i BPP opstår meget ofte i praksis.

Formel definition

Klassen BPP er klassen af prædikater P(x) , der kan beregnes på probabilistiske Turing-maskiner (almindelige Turing-maskiner med et bånd af tilfældige tal) i polynomisk tid med en fejl på højst ⅓. Det betyder, at den probabilistiske Turing-maskine, der beregner værdien af prædikatet, vil give et svar i tid svarende til O(n k ) , hvor n er længden af x , og hvis det rigtige svar er 1, så producerer maskinen 1 med en sandsynlighed på mindst ⅔ og omvendt. Det sæt af ord, som P(x) returnerer 1 på, kaldes det sprog , der genkendes af prædikatet P(x) .

Tallet ⅓ i definitionen er valgt vilkårligt: hvis vi i stedet for det vælger et hvilket som helst tal p , der er strengt taget mindre end ½, får vi den samme klasse. Dette er sandt, fordi hvis der er en Turing-maskine, der genkender et sprog med en fejlsandsynlighed p i O(n k ) tid, så kan nøjagtigheden forbedres vilkårligt godt med en relativt lille stigning i tiden. Hvis vi kører maskinen n gange i træk, og tager resultatet af de fleste kørsler som resultat, så falder fejlsandsynligheden til , og tiden bliver O(n k+1 ) . Her behandles n kørsler af maskinen som et Bernoulli-skema med n forsøg og en sandsynlighed for succes på 1-p , og fejlformlen er sandsynligheden for fejl mindst halvdelen af tiden. Hvis vi nu kører maskinen n 2 gange i træk, så vil tiden stige til O(n k+2 ) , og fejlsandsynligheden falder til . Når eksponenten af det tidsestimerende polynomium stiger, vokser nøjagtigheden således eksponentielt , og enhver ønsket værdi kan opnås. $\left(2{\sqrt {p(1-p)}}\right)^{n}$ $\left(2{\sqrt {p(1-p)}}\right)^{{n^{2}}}$

Monte Carlo algoritmer

En probabilistisk algoritme anvender et sprog i henhold til Monte Carlo-standarden, hvis sandsynligheden for algoritmefejl ikke overstiger . Det vil sige , hvor er prædikatet, at ordet hører til sproget . Klassen BPP er således dannet af prædikater, således at der for dem er en polynomiel probabilistisk algoritme, der tager deres sprog i henhold til Monte Carlo-standarden. Sådanne algoritmer kaldes også Monte Carlo-algoritmer. ${\mathcal {A}}$ $L$ $1/3$ $\mathbb {P} ({\mathcal {A}}(x)=P(x))\geq 2/3$ $P(x)$ $x$ $L$

Forholdet til Las Vegas algoritmer

Lad Monte Carlo-algoritmen med tidskompleksitet , hvor er inputlængden. Vi tager også som den nedre grænse sandsynligheden for, at Las Vegas-algoritmen giver det korrekte resultat, og som en algoritme med tidskompleksitet , der kontrollerer resultatet for pålidelighed. I et sådant tilfælde er der en algoritme med forventet tidskompleksitet . For at bevise det, forestil dig, hvad der forårsager, og indtil det bekræfter rigtigheden af resultatet. Så vil køretiden for en iteration af en sådan procedure være . Sandsynligheden for, at iterationer vil blive gentaget er , hvilket betyder, at det forventede antal iterationer er baseret på, at . ${\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}$

Forhold til andre klasser

Selve BPP er lukket under komplement. Klassen P er inkluderet i BPP, fordi den giver et svar i polynomiel tid med nul fejl. BPP er inkluderet i polynomiehierarkiklassen og er som et resultat inkluderet i PH og PSPACE . Det er også kendt at inkludere BPP i P/Poly-klassen . $\Sigma _{2}^{p}\cap \Pi _{2}^{p}$

Kvantemodstykket til BPP-klassen (med andre ord en udvidelse af BPP-klassen til kvantecomputere ) er BQP-klassen .

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

Andre egenskaber

Indtil 2002 var et af de bedst kendte problemer, der lå i BPP-klassen, primtalsgenkendelsesproblemet , for hvilket der var flere forskellige polynomielle probabilistiske algoritmer, såsom Miller-Rabin-testen , men ingen deterministisk. Men i 2002 blev en deterministisk polynomial algoritme fundet af de indiske matematikere Agrawal, Kayan og Saxena, som dermed beviste, at problemet med at genkende et primtal ligger i klassen P . Deres foreslåede AKS-algoritme (opkaldt efter de første bogstaver i deres efternavne) genkender primeness af et tal med længden n i O(n 4 ) tid .

Kompleksitetsklasser af algoritmer
Betragtes som lys	DLOGTIME AC 0 ACC 0 TC0 [ da L SL RL NL NC SC CC P P-komplet ZPP RP BPP BQP EQP APX
Formodes at være svært	U.P. NP NP komplet co-NP co-NP-komplet AM M.A. QMA PH ⊕P PP #P #P- IP PSPACE PSPACE-komplet
Anses for vanskelig	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY R PR RE RE-complete Co-RE Co-RE-complete ALLE