ZPP

Nella teoria della complessità computazionale, ZPP (Zero-error Probabilistic Polynomial time, "tempo polinomiale probabilistico con errore zero") è la classe di complessità dei problemi per i quali esiste una macchina di Turing probabilistica con queste proprietà * Restituisce sempre la risposta corretta SÌ o NO. * Il tempo di esecuzione è polinomiale in termini di aspettativa per ogni input. In altre parole, se l'algoritmo può lanciare una moneta veramente casuale mentre è in esecuzione, restituirà sempre la risposta corretta e, per un problema di dimensione n, c'è un qualche polinomio p(n) tale che il tempo medio di esecuzione sarà minore di p(n), anche se potrebbe essere occasionalmente molto più lungo. Tale algoritmo è chiamato . Alternativamente, ZPP può essere definita come la classe dei problemi per i quali esiste una macchina di Turing probabilistica con queste proprietà: * Funziona sempre in tempo polinomiale. * Restituisce una risposta SÌ, NO o NON SO. * La risposta è sempre o NON SO o la risposta corretta. * Restituisce NON SO con probabilità al massimo 1/2 (e la risposta corretta altrimenti). Le due definizioni sono equivalenti. La definizione di ZPP si basa sulle macchine di Turing probabilistiche, ma, per chiarezza, si noti che altre classi di complessità basate si di esse includono BPP ed RP. La classe BQP è basata su un'altra macchina dotata di casualità: il computer quantistico.