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

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 game s constrained to bet on strings in lexicographic order. We show that if str ong pseudorandom number generators exist, then betting games are equivalent to martingales for measure on E and EXP. However, we construct betting gam es that succeed on certain classes whose Lutz measures are important open p roblems: 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 t he "finite union property" possessed by Lutz's measure, one obtains the non relativizable consequence BPP not equal EXP. We also show that if EXP not e qual MA, then the polynomial-time truth-table-autoreducible languages have Lutz measure zero, whereas if EXP = BPP, they have measure one.