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 con dimensione dell'input , si definisce , l'insieme dei linguaggi per i quali esiste una macchina di Turing probabilistica , nel tempo , tale che per ogni parola : . .

Allora si può definire RP come: .

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 , si può ridurre la probabilità di errore a nel caso in cui (pur conservando una risposta sicura nel caso ).

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:

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

Con le altre classi probabilistiche

Le inclusioni seguenti mettono in gioco le classi ZPP e 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 ().

Note

Bibliografia

Collegamenti esterni Classe RP su Complexity Zoo

Categoria:Classi di complessità probabilistiche