title: RP (complessità)
text: # 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$
  
  $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).
  
  Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikipedia.org/v1/":): {\displaystyle 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.
  
  $L$
  
  $L$
  
  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.
  
  $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)).
  
  