Třída RP

Budeme předpokládat, že jazyk L patří do třídy RP ("randomized polynomial class" - náhodný polynom), pokud to umožňuje pravděpodobnostní Turingův stroj M , pro který jsou splněny následující podmínky:

• Pokud w nepatří do L, pak pravděpodobnost , že M připustí w, je 0.
• Jestliže w patří k L, pak pravděpodobnost, že M připustí w, je alespoň ½.
• Existuje polynom p(n), pro který, je-li w délky n, pak se vyhodnocení M zastaví po nejvýše p(n) krocích (bez ohledu na obsah náhodné pásky).

Poznámka. Definice třídy RP používá dva pojmy, které spolu nesouvisí:

• Položky 1 a 2 definují náhodný Turingův stroj, který se nazývá stroj typu Monte Carlo .
• Bod 3 hovoří o době chodu, která nezávisí na tom, zda daný Turingův stroj je stroj Monte Carlo.

Poznámka. Volba ½ jako prahové hodnoty v tomto případě není povinná a tuto konstantu lze nahradit jinou (0 < < 1). V tomto případě bude RP obsahovat stejné úkoly, ale změní se jazyky definované konkrétními randomizovanými Turingovými stroji.

Související třídy složitosti

Pokud Turingův stroj M odpoví „Ano“, pak je to zaručeně pravda, zatímco „Ne“ platí jen v některých případech. Třída složitosti co-RP je definována podobně, jen s tím rozdílem, že odpověď „Ne“ je zaručenou pravdou a „Ano“ neplatí vždy. Třída BPP popisuje algoritmy, které mohou dát špatnou odpověď v obou případech. Třída, která je průsečíkem RP a co-RP, se nazývá ZPP .

Vztah s P a NP

Třída P je podmnožinou třídy RP, která je zase podmnožinou třídy NP . Včetně P je podmnožinou Co-RP , což je podmnožinou Co-NP . Není však přesně známo, zda jsou tyto inkluze přísné. Většina výzkumníků se přiklání k verzi, že P ≠ RP nebo RP ≠ NP , jinak P = NP (většina vědců se přiklání k názoru, že to není pravda). Není také známo, zda je RP = Co-RP pravdivé a zda je RP podmnožinou průsečíku NP a Co-NP .

Pozoruhodným příkladem problému, který leží v Co-RP , ale není známo, zda leží v P , je problém kontroly rovnosti dvou polynomů : určit, zda je výraz s několika celočíselnými proměnnými shodně nulový v polynom. Například x · x  − y · y  − ( x + y ) · ( x − y ) je identická nula, zatímco x · x + y · y  není.