A generalization of resource-bounded measure, with application to the BPP VS. EXP problem

Abstract

We introduce resource-bounded betting games and propose a generalization of Lutz's resource-bounded measure in which the choice of the 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 pseudorandom number generators exist, then betting games are equivalent to martingales for measure on E and EXP. However, we construct betting games that succeed on certain classes whose Lutz measures are important open problems: the class of polynomial-time Turing-complete languages in EXP and its superclass of polynomial-time Turing-autoreducible languages. If an EXP-martingale succeeds on either of these classes, or if betting games have the "finite union property" possessed by Lutz's measure, one obtains the nonrelativizable consequence BPP ≠ EXP. We also show that if EXP ≠ MA, then the polynomial-time truth-table-autoreducible languages have Lutz measure zero, whereas if EXP = BPP, they have measure one. © 2000 Society for Industrial and Applied Mathematics.