Pagina Radice del Progetto: Classi Randomizzate

Fatti da conoscere:

definizione di BPP, RP, coRP, ZPP;
conoscere almeno un esempio di algoritmo Monte Carlo, e di un Algortimo Las Vegas.
tecnica delle prove ripetute (RP), e del majority vote (BPP) per ridurre la probabilità di errore;
BPP contenuto in PSC;
BPP contenuto nel secondo livello della gerarchia polinomiale;

Approfondire uno dei seguenti due argomenti, dei quali il secondo è ambizioso:

approfondimento sulle random sources; (partire dal Papadimitriou ed atterrare sui lavori di Vazirani. Lavori recenti di rassegna disponibili alla pagina di Luca Trevisan);
lavoro di Luca Trevisan per la simulazione di BPP.

Come riferimento, consiglio comunque di partire dal libro:

Christos H. Papadimitriou,
Computational Complexity,
Addison-Wesley Publishing Company, Reading, MA, (1994).
ISBN: 0-201-53082-1

Più precisamente:

il Capitolo 11 Randomized Computation.

created: 7 aprile 2003
updated: 7 aprile 2003