Classe ZPP

16 maio 2011, 10:00 • José Félix Costa

Estudos sobre a classe ZPP: algoritmos de «Las Vegas».

Proposição: A classe ZPP está fechada para a complementação, união e intersecção.

Proposição: ZPP = R inters. co-R.

Proposição: P incl. ZPP incl. NP inters. co-NP.

Síntese das classes polinomiais.