On the resource bounded measure of P/poly
Johannes Köbler, Wolfgang F. Lindner · 2002
We show that the class of sets having polynomial size circuits, P/poly, has EXP/sup NP/-measure zero under each of the following two assumptions: EXP/sup NP//spl ne/ZPP(/spl Sigma//sub 2//sup p/)(which holds if the polynomial time hierarchy does not collapse to ZPP(/spl Sigma//sub 2//sup p/)), or NP is not small (does not have EXP-measure zero).