Cesko.wiki BPP (třída složitosti)
Author
Albert FloresV 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 N1000000).
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). +more Pravděpodobnost přijetí 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í , kde místo ANO, dává hodnotu 1 odpověď NE. Garantem příslušnosti problému/jazyka do třídy BPP je algoritmus a , kde pro libovolné je a pro libovolné je .
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.