RP osztály

Feltételezzük, hogy az L nyelv az RP osztályba tartozik ("randomized polynomial class" - véletlenszerű polinom), ha ezt az M valószínűségi Turing-gép lehetővé teszi , amelyre a következő feltételek teljesülnek:

• Ha w nem tartozik L-hez, akkor annak a valószínűsége , hogy M elfogadja w-t, 0.
• Ha w L-hez tartozik, akkor annak a valószínűsége, hogy M elismeri w-t, legalább ½.
• Van egy p(n) polinom, amelyre, ha w n hosszú, akkor M kiértékelése legfeljebb p(n) lépés után leáll (függetlenül a véletlenszerű szalag tartalmától).

Jegyzet. Az RP osztály definíciója két olyan fogalmat használ, amelyek nem kapcsolódnak egymáshoz:

• Az 1. és 2. pont egy véletlenszerű Turing-gépet határoz meg, amelyet Monte Carlo típusú gépnek nevezünk .
• A 3. pont a futási időről szól, ami nem függ attól, hogy az adott Turing gép Monte Carlo gép-e.

Jegyzet. A ½ küszöbként való megválasztása ebben az esetben nem kötelező, és ez az állandó helyettesíthető egy másikkal (0 < < 1). Ebben az esetben az RP ugyanazokat a feladatokat tartalmazza, de a véletlenszerű Turing-gépek által meghatározott nyelvek megváltoznak.

Kapcsolódó összetettségi osztályok

Ha az M Turing-gép „Igen”-t válaszol, akkor ez garantáltan igaz, míg a „Nem” csak bizonyos esetekben igaz. A co-RP komplexitási osztályt hasonlóan határozzák meg, azzal az egyetlen különbséggel, hogy a „Nem” válasz garantált igazság, és az „Igen” nem mindig igaz. A BPP osztály olyan algoritmusokat ír le, amelyek mindkét esetben rossz választ adhatnak. Azt az osztályt, amely az RP és a co-RP metszéspontja, ZPP -nek nevezzük .

Kapcsolat P-vel és NP-vel

A P osztály az RP osztály részhalmaza, amely viszont az NP osztály részhalmaza . Beleértve, P a Co-RP részhalmaza , amely a Co-NP részhalmaza . Azt azonban nem tudni, hogy ezek a zárványok szigorúak-e. A legtöbb kutató arra a verzióra hajlik, hogy P ≠ RP vagy RP ≠ NP , egyébként P = NP (a legtöbb tudós hajlamos azt hinni, hogy ez nem igaz). Az sem ismert, hogy RP = Co-RP igaz- e, és hogy RP az NP és a Co-NP metszéspontjának egy részhalmaza .

A Co-RP- ben rejlő probléma szembetűnő példája , de nem tudni, hogy P -ben van-e, két polinom egyenlőségének ellenőrzésének problémája : annak meghatározása, hogy egy több egész változót tartalmazó kifejezés azonos-e nulla egy polinom. Például x · x  − y · y  − ( x + y ) · ( x − y ) az azonos nulla, míg x · x + y · y  nem.