Timeline
Chat
Prospettiva
RP (complessità)
classe di complessità Da Wikipedia, l'enciclopedia libera
Remove ads
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
Riepilogo
Prospettiva
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)[1].
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 ).
Remove ads
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
Riepilogo
Prospettiva
Con le classi "classiche"
Si ha la relazione seguente con le classi P e NP:
Dimostrazione
Si utilizza la definizione di macchina di Turing probabilistica con nastro casuale.
: basta fare il calcolo della macchina da P (ignorando il nastro casuale); la probabilità di errore è allora nulla nei due casi (appartenenza o no).
: sia M una macchina in tempo polinomiale randomizzata che decide . 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 . Reciprocamente, se la parola è in , 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

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").
Remove ads
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.
Remove ads
Storia
La classe di complessità RP fu introdotta da John Gill[2] nell'articolo Computational complexity of probabilistic Turing machines (Gill (1977)).
Note
Bibliografia
Collegamenti esterni
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads