BPP-luokka

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 10. elokuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Algoritmien teoriassa kompleksisuusluokka BPP ( englannin sanasta bounded -error, probabilistic, polynomial ) on predikaattien luokka , joka on nopeasti (polynomiajassa) laskettavissa ja antaa vastauksen suurella todennäköisyydellä (lisäksi aikaa uhraamalla voit saavuttaa mielivaltaisen suuren vastauksen tarkkuuden). Probabilistisilla menetelmillä ratkaistuja ja BPP:ssä valehtelevia ongelmia ilmenee käytännössä hyvin usein.

Muodollinen määritelmä

Luokka BPP on predikaattien P(x) luokka, jotka voidaan laskea todennäköisyyspohjaisilla Turingin koneilla (tavallisilla Turingin koneilla , joissa on satunnaislukunauha) polynomiajassa virheellä enintään ⅓. Tämä tarkoittaa, että todennäköisyyspohjainen Turingin kone, joka laskee predikaatin arvon, antaa vastauksen ajassa, joka on yhtä suuri kuin O(n k ) , missä n on x :n pituus , ja jos oikea vastaus on 1, niin kone tuottaa 1:n todennäköisyydellä vähintään ⅔ ja päinvastoin. Sanajoukkoa , jolle P(x) palauttaa arvon 1, kutsutaan predikaatin P(x) tunnistamaksi kieleksi .

Määritelmän luku ⅓ valitaan mielivaltaisesti: jos sen sijaan valitaan mikä tahansa luku p , joka on tiukasti pienempi kuin ½, niin saadaan sama luokka. Tämä pitää paikkansa, koska jos on olemassa Turingin kone, joka tunnistaa kielen virhetodennäköisyydellä p O(n k ) ajassa , niin tarkkuutta voidaan parantaa mielivaltaisesti hyvin suhteellisen pienellä lisäyksellä ajassa. Jos ajetaan konetta n kertaa peräkkäin ja otetaan tulokseksi useimpien ajojen tulos, niin virhetodennäköisyys putoaa arvoon , ja ajasta tulee O(n k+1 ) . Tässä koneen n ajoa käsitellään Bernoullin mallina, jossa on n yritystä ja onnistumistodennäköisyys 1-p , ja virhekaava on epäonnistumisen todennäköisyys vähintään puolet ajasta. Jos nyt ajetaan konetta n 2 kertaa peräkkäin, niin aika kasvaa arvoon O(n k+2 ) ja virhetodennäköisyys putoaa arvoon . Näin ollen, kun aikaa estimoivan polynomin eksponentti kasvaa, tarkkuus kasvaa eksponentiaalisesti ja mikä tahansa haluttu arvo voidaan saavuttaa. $\left(2{\sqrt {p(1-p)}}\oikea)^{n}$ $\left(2{\sqrt {p(1-p)}}\right)^{{n^{2}}}$

Monte Carlo -algoritmit

Probabilistinen algoritmi ottaa käyttöön Monte Carlon standardin mukaisen kielen , jos algoritmin virhetodennäköisyys ei ylitä . Eli , missä on predikaatti, että sana kuuluu kieleen . Näin ollen luokka BPP muodostuu predikaateista siten, että niille on olemassa polynominen todennäköisyysalgoritmi, joka ottaa heidän kielensä Monte Carlon standardin mukaan. Tällaisia algoritmeja kutsutaan myös Monte Carlo -algoritmeiksi. ${\mathcal {A}}$ $L$ $1/3$ $\mathbb {P} ({\mathcal {A}}(x)=P(x))\geq 2/3$ $P(x)$ $x$ $L$

Suhde Las Vegasin algoritmeihin

Olkoon Monte Carlo -algoritmi aikakompleksisuudella , missä on syötteen pituus. Otamme myös alarajaksi todennäköisyyden, että Las Vegasin algoritmi antaa oikean tuloksen, ja algoritmiksi, jonka aikamonimutkaisuus , joka tarkistaa tuloksen luotettavuuden. Tällaisessa tapauksessa on olemassa algoritmi , jolla on odotettu aikamonimutkaisuus . Todistaaksesi sen, kuvittele, mikä aiheuttaa ja kunnes se vahvistaa tuloksen oikeellisuuden. Tällöin tällaisen proseduurin yhden iteraation ajoaika on . Todennäköisyys sille, että iteraatiot toistetaan, on , mikä tarkoittaa, että iteraatioiden odotettu määrä on perustuen siihen, että . ${\mathcal {B}}$ $f(n)$ $p(n)$ $\mathcal{A}$ ${\mathcal {C}}$ $g(n)$ $\mathcal{A}$ $\mathcal{A}$ ${\näyttötyyli (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)$ ${\displaystyle \sum _{k=1}^{\infty }k\cdot x^{k}=x/(1-x)^{2))$

Suhteet muihin luokkiin

Itse BPP on suljettu täydennyksen alla. Luokka P sisältyy BPP:hen, koska se antaa vastauksen polynomiajassa nollavirheellä. BPP sisältyy polynomihierarkialuokkaan , ja sen seurauksena se sisältyy PH- ja PSPACE -luokkaan . BPP:n tiedetään myös sisällyttävän P/Poly-luokkaan . $\Sigma _{2}^{p}\cap \Pi _{2}^{p}$

BPP-luokan kvanttivastine (eli BPP-luokan laajennus kvanttitietokoneisiin ) on BQP-luokka .

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

Muut ominaisuudet

Vuoteen 2002 asti yksi tunnetuimmista BPP-luokan ongelmista oli alkulukujen tunnistusongelma , jolle oli olemassa useita erilaisia polynomisia todennäköisyysalgoritmeja, kuten Miller-Rabinin testi , mutta yksikään ei ollut deterministinen. Vuonna 2002 intialaiset matemaatikot Agrawal, Kayan ja Saxena löysivät kuitenkin deterministisen polynomialgoritmin , joka osoitti, että alkuluvun tunnistamisongelma on luokassa P . Heidän ehdottamansa AKS-algoritmi (nimetty heidän sukunimiensä ensimmäisten kirjainten mukaan) tunnistaa n -pituisen luvun ensisijaisuuden O (n 4 ) -ajassa .

Algoritmien monimutkaisuusluokat
Kevyenä pidetty	DLOGTIME AC 0 ACC 0 TC0 [ fi L SL RL NL NC SC CC P P-täydellinen ZPP RP BPP BQP EQP APX
Taitaa olla vaikeaa	U.P. NP NP valmis co-NP co-NP-täydellinen AM M.A. QMA PH ⊕P PP #P #P - IP_ PSPACE PSPACE-täydellinen
Vaikeaksi pidetty	EXPTIME NEXPTIME EXPACE 2-EXPTIME ELEMENTARY R PR RE täytä uudelleen Co-RE Co-RE-complete KAIKKI