TY - GEN
T1 - A generalization of resource-bounded measure, with an application (extended abstract)
AU - Buhrman, Harry
AU - Van Melkebeek, Dieter
AU - Regan, Kenneth W.
AU - Sivakumar, D.
AU - Strauss, Martin
PY - 1998
Y1 - 1998
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/78649846952
U2 - 10.1007/BFb0028558
DO - 10.1007/BFb0028558
M3 - Conference contribution
AN - SCOPUS:78649846952
SN - 3540642307
SN - 9783540642305
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 161
EP - 171
BT - STACS 98 - 15th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
T2 - 15th Annual Symposium on Theoretical Aspects of Computer Science, STACS 98
Y2 - 25 February 1998 through 27 February 1998
ER -