Algoritmos Probabilísticos: Exercícios

18 maio 2011, 14:00 • José Félix Costa

Exercício: Mostre que se A é decidível por uma máquina de Turing probabilística polinomial de três outputs, com probabilidade de erro 0 e probabilidade epsilon < 1 de não dar resposta, então A está em ZPP.

Exercício: Mostre que a classe ZPP está fechada para a complementação, intersecção e união.

Exercício: Mostre que as classes BPP, R e ZPP são fechadas para a redução-m.