RP (complessità)

Nella teoria della complessità computazionale, RP (Randomized Polynomial time, "tempo polinomiale randomizzato") è la classe di complessità dei problemi decisionali eseguiti su una macchina di Turing probabilistica.

Si può inoltre definire una classe molto vicina: co-RP.

La classe RP è l'insieme dei problemi, o in modo equivalente dei linguaggi, per i quali esiste una macchina di Turing probabilistica in tempo polinomiale che soddisfa le seguenti condizioni di accettazione:

• Se la parola non è nel linguaggio, la macchina la rifiuta.
• Se la parola è nel linguaggio, la macchina l'accetta con una probabilità superiore a 1/2.

Si dice che la macchina "sbaglia solo da un lato".

Per un polinomio ${\displaystyle T}$ con dimensione dell'input ${\displaystyle n}$, si definisce ${\displaystyle RTIME(T(n))}$, l'insieme dei linguaggi ${\displaystyle L}$ per i quali esiste una macchina di Turing probabilistica ${\displaystyle M_{L}}$, nel tempo ${\displaystyle T(n)}$, tale che per ogni parola ${\displaystyle x}$ :

• ${\displaystyle x\notin L\Rightarrow Pr(M_{L}(x)=0)=1}$ .
• ${\displaystyle x\in L\Rightarrow Pr(M_{L}(x)=1)\geq {\frac {1}{2}}}$.

Allora si può definire RP come: ${\displaystyle RP=\cup _{p\in N}RTIME(n^{p})}$.

La costante 1/2 è in realtà arbitraria, si può scegliere qualsiasi numero (costante) tra 0 e 1 (esclusi)^[1].

L'idea è che eseguendo il calcolo indipendentemente un numero polinomiale di volte ${\displaystyle p(n)}$, si può ridurre la probabilità di errore a ${\displaystyle \left({\frac {1}{2}}\right)^{p(n)}}$ nel caso in cui ${\displaystyle x\in L}$ (pur conservando una risposta sicura nel caso ${\displaystyle x\not \in L}$).

La classe co-RP è l'insieme di linguaggi per i quali esiste una macchina di Turing probabilistica in tempo polinomiale che soddisfa le seguenti condizioni di accettazione:

• Se la parola è nel linguaggio, la macchina l'accetta.
• Se la parola non è nel linguaggio, la macchina lo rifiuta con una probabilità superiore a 1/2.

(Stessa osservazione per la costante.)

Si ha la relazione seguente con le classi P e NP: ${\displaystyle P\subseteq RP\subseteq NP}$

Osserviamo che questa classe non è più interessante se P=NP.

Le inclusioni seguenti mettono in gioco le classi ZPP e BPP.

${\displaystyle ZPP\subseteq RP\subseteq BPP}$

Questo discende direttamente dalle definizioni: ZPP è l'intersezione di RP e di co-RP e BPP con condizioni di accettazione meno stringenti (errore "dai due lati").

Quelli di RP sono problemi per i quali esiste un algoritmo probabilistico che soddisfa le condizioni descritte sopra.

Per esempio il problema di sapere se un numero intero è primo è nella classe di complessità co-RP grazie al test di primalità di Miller-Rabin. Infatti, questo problema è lo stesso in P, grazie al test di primalità AKS.

Un problema di co-RP che non è conosciuto essere in P è il problema della "verifica dell'identià ponomiale" (polynomial identity testing), che consiste, dato un polinomio multivariato sotto una qualsiasi forma, nel decidere se esso è identicamente nullo o no. Grazie al lemma di Schwartz–Zippel, si possono riconoscere i polinomi nulli con una buona probabilità valutandoli in un piccolo numero di punti.

La classe di complessità RP fu introdotta da John Gill^[2] nell'articolo Computational complexity of probabilistic Turing machines (Gill (1977)).

• Sanjeev Arora e Boaz Barak, Computational Complexity: A modern Approach, Cambridge University Press, 2009, ISBN 0-521-42426-7.
• (EN) John Gill, Computational complexity of probabilistic Turing machines, in SIAM Journal on Computing, vol. 6, n. 4, 1977, pp. 675-695.

• (EN) Classe RP Archiviato il 21 luglio 2017 in Internet Archive. su Complexity Zoo

V · D · M Classi di complessità (elenco)
P · NP · co-NP · NP-C · co-NP-C · NP-hard · UP · #P · #P-C · L · NL · NC · P-C · PSPACE · PSPACE-C · EXPTIME · EXPSPACE · PR · RE · Co-RE · RE-C · Co-RE-C · R · BQP · BPP · RP · ZPP · PCP · IP · PH