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 Barita, Probableca, Polinomia tempo.
| BPP algoritmo (1 rulo) | ||
|---|---|---|
| Probableco de respondo produktita | ||
| Ĝusta respondo |
Jes | Ne |
| Jes | ≥2/3 | ≤1/3 |
| Ne | ≤1/3 | ≥2/3 |
| BPP algoritmo (n ruloj) | ||
| Probableco de respondo produktita | ||
| Ĝusta respondo |
Jes | Ne |
| Jes | > 1-e-n/18 | < e-n/18 |
| Ne | < e-n/18 | > 1-e-n/18 |
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 [1]. Ĉ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 redakti
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 BPP [2] (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 redakti
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 redakti
- Princeton Cs 597E: Malhazardiga papera listo
- Harvard Cs 225: Pseŭdohazardeco Arkivigite je 2003-08-05 per la retarkivo Wayback Machine
Referencoj redakti
- 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. COI:10.1145/258533.258590