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.

Definizione

Una prima definizione

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".

Definizione formale

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

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

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

Il ruolo della costante

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

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

La classe co-RP

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.)

Relazioni con le altre classi

Con le classi "classiche"

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

Dimostrazione

Si utilizza la definizione di macchina di Turing probabilistica con nastro casuale.

$P\subseteq RP$: basta fare il calcolo della macchina da P (ignorando il nastro casuale); la probabilità di errore è allora nulla nei due casi (appartenenza o no).

$RP\subseteq NP$: sia M una macchina in tempo polinomiale randomizzata che decide $L\in RP$. Si costruisce una macchina M' di NP che prevede un nastro casuale tale che M accetta. Se il nastro previsto fa veramente accettare M, allora M' accetta, altrimenti rifiuta.

Se esiste un nastro "buono", perché M non sbaglia, la parola considerata è in $L$. Reciprocamente, se la parola è in $L$, M accetta con una probabilità di almeno 1/2, cioè M accetta sulla metà dei nastri casuali; esiste dunque almeno un nastro casuale che fa accettare e quindi M' lo prevede e accetta.

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

Con le altre classi probabilistiche

Inclusioni di classi di complessità probabilistiche

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

$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").

Problemi in RP e co-RP

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.

Storia

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

Bibliografia

• 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.

Collegamenti esterni

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