We introduce "resource-bounded betting games", and propose
a generalization of Lutz's resource-bounded measure in which the choice
of next string to bet on is fully adaptive. Lutz's martingales are
equivalent to betting games constrained to bet on strings in lexicographic
order. We show that if strong pseudo-random number generators exist,
more >>>

This paper proves that if strong pseudorandom number generators or
one-way functions exist, then the class of languages that have
polynomial-sized circuits is not small within exponential
time, in terms of the resource-bounded measure theory of Lutz.
More precisely, if for some \epsilon > 0 there exist nonuniformly
2^{n^{\epsilon}}-hard ... more >>>