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)\ge \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\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$

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

Con le altre classi probabilistiche

Errore nella creazione della miniatura:

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 (Template:Cita).

Bibliografia

• Template:Cita testo
• Template:Cita libro

Collegamenti esterni

• Template:En Classe RP Template:Webarchive su Complexity Zoo