Conselhos

23 maio 2011, 10:00 • José Félix Costa

Conselhos

Classes de complexidade definidas à custa de classes de conselhos: classes não uniformes C/F.

P/log,  P/poly, PSPACE/poly.

Versões de HALT e SAT em P/poly.

Proposição: Se SAT está em P/log, então P = NP.