Cesko.wiki RP (třída složitosti)
Author
Albert FloresV 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 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 RP je algoritmus a , kde pro libovolné je a pro libovolné je .
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. +more Více o tomto problému najdete v článku Problém P versus NP.