RP (třída složitosti)

V teorii složitosti je RP 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 na kladné odpovědi stroje je možno se spolehnout.

RP je obvykle považována za třídu problémů, které jsou efektivně řešitelné (existují ale i další třídy považované za efektivně řešitelné, jako P a BPP), přesto není v této třídě problém najít 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 RP je algoritmus a q>½, kde pro libovolné x∈L je p^A(x)>q a pro libovolné x∉L je p^A(x)=0.

Různá značení

Označení třídy v literatuře není zcela jednotné.

Známé problémy třídy RP

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.

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

Podmnožinou RP je P (P stroj nesmí náhodný generátor využívat, každý P stroj je i RP strojem).

Nadmnožinou je RP je BPP, (každý RP stroj kde odpovědi NEVÍM jsou nahrazeny odpověďmi NE je BPP strojem).

Známější nadmnožinou RP je NP, což je třída problémů rozhodnutelných v polynomiálním čase na nedeterministickém Turingově stroji (každý RP stroj je NP strojem).

Vztah tříd P a NP není dosud vyřešen, je možné, že se tyto třídy rovnají. Přestože důkaz zatím neexistuje, většina expertů věří, že P je vlastní podmnožinou NP. Více o tomto problému najdete v článku Problém P versus NP.