RP Randomizzati in tempo polinomiale è la complessità della classe di teoria della complessità, i problemi per i quali una macchina di Turing probabilistica esiste con queste proprietà:⁕sempre eseguito in tempo polinomiale nella dimensione di input⁕Se la risposta corretta è NO, si ritorna sempre NON⁕Se la risposta corretta è SÌ, allora restituisce SÌ con una probabilità di almeno 1/2.In altre parole, l’algoritmo è permesso di capovolgere una veramente casuale moneta mentre è in esecuzione. L’unico caso in cui l’algoritmo può restituire SÌ è se la risposta effettiva è SÌ; pertanto, se l’algoritmo termina e produce SÌ, la risposta corretta è sicuramente SÌ; tuttavia, l’algoritmo può terminare con NO indipendentemente dalla risposta effettiva. Cioè, se l’algoritmo restituisce NO, potrebbe essere sbagliato.Alcuni autori chiamano questa classe R, anche se questo nome è più comunemente usato per la classe di linguaggi ricorsivi.Se la risposta corretta è SÌ e l’algoritmo viene eseguito n volte con il risultato di ogni esecuzione statisticamente indipendente dagli altri, restituirà SÌ almeno una volta con probabilità almeno 1 − 2−. Quindi, se l’algoritmo viene eseguito 100 volte, allora la possibilità che dia la risposta sbagliata ogni volta è inferiore alla possibilità che i raggi cosmici corrompano la memoria del computer che esegue l’algoritmo. In questo senso, se è disponibile una fonte di numeri casuali, la maggior parte degli algoritmi in RP sono altamente pratici.

vedi di più ”