Circuitos polinomiais

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

Proposição : P/poly = UNIÃO {S esparso} P(S).
Proposição : BPP tem circuitos polinomiais.
Proposição : R tem circuitos polinomiais.
Proposição : ZPP tem circuitos polinomiais.