BPP (komplikeco)

Ĉi tiu artikolo bezonas poluradon, ĉar ĝi montras stilajn kaj/aŭ gramatikajn kaj/aŭ strukturajn problemojn, kiuj ne konformas al stilogvido. La priskribo de la problemo troviĝas ĉi tie. Bonvolu ŝanĝi la enhavon por plibonigi la artikolon.

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.

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.

1. ↑ [1]