m oprava dvěmi → dvěma, kosmetické změny za použití AWB
Řádek 4:
== Upřesnění definice ==
Randomizovaný Turingův stroj není obvyklý standardizovaný pojem. Pro naši definici stačí nedeterministický stroj, s nejvýš dvěmidvě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í {{math|p<sup>A</sup>}} 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í {{math|p<sup>R</sup>}}, kde místo ANO, dává hodnotu 1 odpověď NE. Garantem příslušnosti problému/jazyka {{math|L}} do třídy '''RP''' je algoritmus a {{math|q>½}}, kde pro libovolné {{math|x∈L}} je {{math|p<sup>A</sup>(x)>q}} a pro libovolné {{math|x∉L}} je {{math|p<sup>A</sup>(x){{=}}0}}.
== Různá značení ==
Řádek 10:
== Známé problémy třídy RP ==
[[Millerův-Rabinův_test_prvočíselnosti|Millerův-Rabinův test prvočíselnosti]] použitý v negaci k testování složenosti čísla byl dlouhou dobu argumentem pro to, aby testování složenosti čísla byl dobrým příkladem problému z '''RP'''. Vzhledem k tomu, že již víme, že testování složenosti/prvočíselnosti patří do '''P''' (což je podmnožinou '''RP'''), není to vhodný příklad.
V současnosti je znám algoritmus na testování různosti polynomů více proměnných nad celými čísly (v obecném tvaru), který garantuje příslušnost tohoto problému do '''RP'''. Není přitom znám polynomiální algoritmus.
