Wikipedie

RP (třída složitosti): Porovnání verzí

Interaktivně procházet historii
← Přejít na předchozí porovnáníPřejít na další porovnání →
Smazaný obsah Přidaný obsah
VizuálníWikitext
Hippo.69 (diskuse | příspěvky)
220 editací
Hippo.69 (diskuse | příspěvky)
220 editací
Link Miller Rabin
Řádek 10:
 
== Známé problémy třídy RP ==
[[Millerův-Rabinův_test_prvočíselnosti|Millerův-Rabinův algoritmustest prvočíselnosti]] testování provočí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.
Citováno z „https://cs.wikipedia.org/wiki/RP_(třída_složitosti)“