Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR98-058 | 2nd August 1998 00:00

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 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,
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.

ISSN 1433-8092 | Imprint