- Authors: H. Buhrman, D. van Melkebeek, K. Regan, D. Sivakumar, and M. Strauss.
- Reference:
*SIAM Journal on Computing*, 30(2): 576-601, 2000. - Earlier version:
- A Generalization of Resource-Bounded Measure, With an Application.
In
*Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science*, p. 161-171, 1998.

- A Generalization of Resource-Bounded Measure, With an Application.
In

We show that if strong pseudo-random 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 non-relativizable 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.

dieter@cs.wisc.edu