Algoritmos Probabilísticos: Exercícios

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

Exercício: Mostre que

(a) P incl. R;

(b) P incl co-R;

(c) R incl. NP;

(d) co-R incl. co-NP;

(e) R incl. BPP;

(f) co-R incl. BPP.

Exercício: Mostre que as seguintes classes estão fechadas para a redução de muitos para um em tempo polinomial:

(a) PP;

(b) BPP;

(c) R;

(d) co-R.

Exercício: Mostre que se NP incl. BPP, então R = NP.