Conselhos

17 Maio 2011, 10:00 José Félix Costa

Construção das classes probabilísticas por conselhos

Conselhos, conselhos correctos para um conjunto. Conselhos pequenos.

Proposição: As asserções seguintes são equivalentes: (a) A está em BPP, (b) Para todo o polinómio q, há um conjunto B em P e um polinómio p tais que, entre as palavras de tamanho p(n), existem pelo menos 2^p(n) ( 1 - (1/2)^q(n) ) conselhos correctos para A, para palavras de tamanho n.

Proposição: 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 (a) se x in A então <x,y> in Q para mais de 1/2 das palavras y tais que |y| = p(|x|) e (b) se x not in A então <x,y> not in Q para mais de 1/2 das palavras y tais que |y| = p(|x|).

+++++++++++++++++++++++++++++++++++++++++++++++++++++

TPC

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 (a) se x in A então <x,y> in Q para mais de 1/2 das palavras y tais que |y| <= p(|x|) e (b) se x not in A então <x,y> not in Q para mais de 1/2 das palavras y tais que |y| <= p(|x|).

+++++++++++++++++++++++++++++++++++++++++++++++++++++