PP e BPP em conselhos

8 junho 2010, 14:00 • José Félix Costa

Exercício : Mostre que um conjunto A está em PP se e só se existe um conjunto Q em P e um polinómio p, tais que x in A se e só se (x,y) in Q para mais de 1/2 das palavras y tais que |y| = p(|x|).
Exercício : Mostre que um conjunto A está em PP se e só se existe um conjunto Q em P e um polinómio p, tais que x in A se e só se (x,y) in Q para mais de 1/2 das palavras y tais que |y| <= p(|x|).
Exercício : Mostre que um conjunto A está em BPP se e só se existe um conjunto Q em P e um polinómio p, tais que x in A se e só se (x,y) in Q para mais de 3/4 das palavras y tais que |y| = p(|x|).
Exercício : Mostre que um conjunto A está em BPP se e só se existe um conjunto Q em P e um polinómio p, tais que x in A se e só se (x,y) in Q para mais de 3/4 das palavras y tais que |y| <= p(|x|).