V teorii složitosti je PP třída problémů řešitelných pravděpodobnostními Turingovými stroji v polynomiálním čase s pravděpodobností chyby menší než 1/2. Zkratka PP znamená Probabilistic Time Polynomial.
Jazyk L patří do PP právě tehdy, když existuje pravděpodobnostní Turingův stroj M takový, že
Třída BPP je podmnožinou třídy PP ; lze jej považovat za podmnožinu problémů, pro které jsou k dispozici účinné pravděpodobnostní algoritmy. Rozdíl spočívá ve velikosti pravděpodobnosti chyby: ve třídě BPP musí každý algoritmus dát správnou odpověď s pravděpodobností větší než c (c > 1/2), například 2/3 nebo 777/1000. V tomto případě je možné spustit algoritmus pevně stanovený počet opakování a poté vybrat odpověď s největším počtem hlasů, aby se dosáhlo určité pravděpodobnosti správnosti menší než 1. Počet opakování se zvyšuje, jak se c blíží 1/2, ale nezávisí na n .
Komentář. c nemůže záviset na vstupu. Na druhou stranu, algoritmus z PP může provádět následující posloupnost akcí:
Vzhledem k tomu, že tyto dvě možnosti jsou si velmi blízké, zejména pro velké n , i když Turingův stroj běží mnohokrát, je velmi obtížné pochopit, zda pracujeme s možností, kde je správná odpověď "Ano" nebo "Ne" . Pokus o dosažení pevné hodnoty pravděpodobnosti pomocí většinového hlasování vyžaduje počet opakování, který je exponenciální v n . Zhruba se to dá přirovnat k úkolu určit, na kterou stranu mince padne s malou rezervou tím, že ji hodíte velkým počtem hodů.
| Třídy složitosti algoritmů | |
|---|---|
| Považováno za světlo | |
| Prý to bude těžké | |
| Považováno za obtížné |
|