BPP

Nella teoria della complessità computazionale, BPP (Bounded-error Probabilistic Polynomial time, "tempo polinomiale probabilistico con errore limitato") è una classe di complessità a cui appartengono quei problemi decisionali che richiedono un tempo polinomiale per avere una soluzione probabilistica corretta. Più precisamente, essi sono risolvibili in tempo polinomiale da una macchina di Turing probabilistica, con una probabilità di errore al massimo di 1/3 per tutte le istanze. Informalmente, un problema è in BPP se c'è un algoritmo per esso che ha le seguenti proprietà: * È consentito lanciare monete e prendere decisioni casuali * È garantito che sia eseguito in tempo polinomiale * In qualsiasi data esecuzione dell'algoritmo, esso ha una probabilità al più pari a 1/3 di dare la risposta sbagliata, sia che la risposta sia SÌ oppure NO.