BPP (třída složitosti)

V teorii složitosti je BPP jednou z významných tříd složitosti. Obsahuje všechny problémy řešitelné pomocí randomizovaného Turingova stroje v polynomiálním množství času s tím, že pravděpodobnost správné odpovědi je větší než ½ a je možno ji od ½ odrazit konstantou.

BPP je obvykle považována za největší třídu problémů, které jsou efektivně řešitelné (menší třídy považované za efektivně řešitelné jsou P a RP), přesto lze v této třídě nalézt i efektivně neřešitelné problémy (se složitostí například N^1000000).

Upřesnění definice

Randomizovaný Turingův stroj není obvyklý standardizovaný pojem. Pro naši definici stačí nedeterministický stroj, s nejvýš dvěma možnostmi v každém kroku, jehož čas výpočtu je omezen polynomiálním časem a možné odpovědi jsou ANO, NE, NEVÍM (použito i pro nedokončené výpočty). Pravděpodobnost přijetí p^A daného vstupu je možno definovat v kořeni stromu možných výpočtů indukcí od listů stromu, jakožto průměr hodnot následovníků (kde ANO dává hodnotu 1 a ostatní odpovědi 0). Obdobně je možno definovat pravděpodobnost odmítnutí p^R, kde místo ANO, dává hodnotu 1 odpověď NE. Garantem příslušnosti problému/jazyka L do třídy BPP je algoritmus a q>½, kde pro libovolné x∈L je p^A(x)>q a pro libovolné x∉L je p^R(x)>q.

Vztah k dalším složitostním třídám

Podmnožinou BPP je RP (každý RP stroj kde místo odpovědí NEVÍM dáme odpovědi NE je BPP strojem). O vztahu BPP a NP se toho moc neví, museli bychom porovnávat až s dalšími členy Polynomiální hierarchie.