Clasa RP

Vom presupune că limbajul L aparține clasei RP („clasa polinomială aleatorie” - polinom aleatoriu), dacă este permis de mașina probabilistică de Turing M , pentru care sunt îndeplinite următoarele condiții:

• Dacă w nu aparține lui L, atunci probabilitatea ca M să admită w este 0.
• Dacă w aparține lui L, atunci probabilitatea ca M să admită w este de cel puțin ½.
• Există un polinom p(n) pentru care, dacă w este de lungime n, atunci evaluarea lui M se oprește după cel mult p(n) pași (indiferent de conținutul benzii aleatoare).

Notă. Definiția clasei RP folosește două concepte care nu sunt legate:

• Elementele 1 și 2 definesc o mașină Turing randomizată, care se numește o mașină de tip Monte Carlo .
• Punctul 3 vorbește despre timpul de funcționare, care nu depinde de faptul dacă mașina Turing dată este o mașină Monte Carlo.

Notă. Alegerea lui ½ ca prag în acest caz nu este obligatorie și această constantă poate fi înlocuită cu alta (0 < < 1). În acest caz, RP-ul va conține aceleași sarcini, dar limbajele definite de mașinile Turing specifice aleator se vor schimba.

Clase de complexitate înrudite

Dacă mașina Turing M răspunde „Da”, atunci acest lucru este garantat a fi adevărat, în timp ce „Nu” este adevărat numai în unele cazuri. Clasa de complexitate co-RP este definită în mod similar, cu singura diferență că răspunsul „Nu” este un adevăr garantat, iar „Da” nu este întotdeauna adevărat. Clasa BPP descrie algoritmi care pot da un răspuns greșit în ambele cazuri. Clasa care este intersecția dintre RP și co-RP se numește ZPP .

Relația cu P și NP

Clasa P este un subset al clasei RP, care la rândul său este un submult al clasei NP . Inclusiv, P este un subset al Co-RP , care este un subset al Co-NP . Cu toate acestea, nu se știe exact dacă aceste incluziuni sunt stricte. Majoritatea cercetătorilor sunt înclinați către versiunea că P ≠ RP sau RP ≠ NP , în caz contrar P = NP (majoritatea oamenilor de știință sunt înclinați să creadă că acest lucru nu este adevărat). De asemenea, nu se știe dacă RP = Co-RP este adevărat și dacă RP este o submulțime a intersecției dintre NP și Co-NP .

Un exemplu izbitor de problemă care se află în Co-RP , dar nu se știe dacă se află în P , este problema verificării a două polinoame pentru egalitate : pentru a determina dacă o expresie cu mai multe variabile întregi este identic zero în un polinom. De exemplu, x · x  − y · y  − ( x + y ) · ( x − y ) este zero identic, în timp ce x · x + y · y  nu este.