BPP (komplikeco)

En komputa komplikteorio, **BPP** estas la komplikeca klaso de decidaj problemoj solveblaj per probableca maŝino de Turing en polinoma tempo kun erar-probablo de maksimume 1/3 por ĉiuj okazoj. La mallongigo **BPP** estas de ***B**arita, **P**robableca, **P**olinomia tempo*.

Se problemo estas en **BPP**, tiam estas algoritmo por ĝi, al kiu estas permesite klaki monerojn kaj fari hazardaj decidojn. Ĝi estas garantiita al ruliĝi en polinoma tempo. Sur iu ajn donita kuro de la algoritmo, ĝi redonas eraran respondo kun probableco ne pli granda ol 1/3, por ambaŭ okazoj de la vera respondo estas "jes" aŭ "ne".

La elekto de 1/3 en la difino estas ajna. Ĝi povas esti iu ajn konstanto inter 0 kaj 1/2 malinkluzivite de "1/2" kaj la aro **BPP** restas neŝanĝita; tamen, tiu konstanto devas esti sendependa de la enigo. La ideo estas, ke estas probablo de eraro, sed se la algoritmo estas kurita multajn fojojn, la ŝanco, ke la plejparto de la kuroj estas eraraj forfalas eksponente sekve de la baro de Ĉernov . Ĉi tio ebligas krei alte precizan algoritmon nur per kuro de la algoritmo kelkfoje kaj preno de la plejparta rezulto kiel la respondo.

**BPP** estas unu el la plej grandaj *praktikaj* klasoj de problemoj, kio signifas, ke plej problemoj de intereso en BPP havas kompetentajn probablecajn algoritmojn, kiuj povas esti kuritaj rapide sur realaj modernaj maŝinoj, per la maniero priskribita pli supre. Pro ĉi tiu kaŭzo estas de granda praktika intereso kiuj problemoj kaj klasoj de problemoj estas en **BPP**.

## Interrilato al aliaj kompleksecaj klasoj 
Estas sciate, ke **BPP** estas fermita sub komplemento; tio estas, **BPP**=**Co-BPP**. Estas malfermita demando, ĉu **BPP** estas subaro de **NP**. Estas ankaŭ malfermita demando ĉu **NP** estas subaro de **BPP**; se ĝi estas, tiam **NP**=**RP** kaj **PH** \subseteq **BPP**  (multaj konsideras ĉi tion malverŝajnan, ĉar ĝi devus enhavi praktikajn solvaĵojn por iuj malfacilaj NP-plenaj problemoj). Estas sciate, ke **RP** estas subaro de **BPP**, kaj **BPP** estas subaro de **PP**. Ne estas sciate ĉu tiuj du estas severaj subaroj. **BPP** estas enhavata en **PH**. Se **P**=**NP** do **PH**=**P** kaj do **BPP**=**P**.

La ekzisto de certaj fortaj pseŭdohazardaj nombraj generiloj estas konjektita de plejparto kompetentuloj de la kampo. Ĉi tiu konjekto implicas, ke hazardo ne donas aldonan komputan povon al polinoma tempa kalkulado, tio estas, **P**=**RP**=**BPP**. Notu, ke ordinaraj generiloj ne estas sufiĉaj por montri ĉi tiun rezulton; iu ajn probableca algoritmo realigita uzante tipan hazardan nombran generilon kun fiksita skemo ĉiam produktas malĝustajn rezultojn sur certa enigoj (kvankam ĉi tiuj enigoj povus esti maloftaj). Ni ankaŭ havas ke **P**=**BPP** se **EKSPTEMPO** kolapsiĝas al **E** = *DTEMPO(2O(n))*, aŭ se **E** havas eksponentan funkcian cirkvitan komplikecon (Impagliazzo kaj Wigderson).

## Aliaj propraĵoj 
Delonge, unu de la plej famaj problemoj, kiuj estis sciataj al esti en **BPP** sed ne sciataj al esti en **P** estis la problemo de primeco-testado, determino ĉu donita nombro estas primo. Tamen, estis trovita polinomo-tempa algoritmo por ĉi tiu problemo, tial montranta, ke ĝi estas en **P**.

**BPP** estas malalta por si, kio signifas, ke **BPP**-maŝino kun la povo solvi **BPP**-problemojn tujprete (**BPP** orakola maŝino) estas neniel pli pova ol la maŝino sen ĉi tiu superflua povo.

Ĉi tiu klaso estas difinita por ordinara maŝino de Turing plus fonto de hazardo. La respektiva klaso por kvantuma komputilo estas **BQP**.

Anaro en iu ajn lingvo en **BPP** povas esti difinita per polinomo-ampleksa bulea cirkvito (vidu en cirkvita komplikeco).

## Eksteraj ligiloj 
* Princeton Cs 597E: Malhazardiga papera listo
* Harvard Cs 225: Pseŭdohazardeco 

## Referencoj 
* Russell Impagliazzo kaj Avi Wigderson (1997). "P=BPP if E requires exponential circuits: Derandomizing the XOR Lemma". *Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing*, pp. 220–229. 

Kategorio:Komputa komplikeco