Probabilistic martingales and BPTIME classes
Kenneth W. Regan, D. Sivakumar · 2002
We define probabilistic martingales based on randomized approximation schemes, and show that the resulting notion of probabilistic measure has several desirable robustness properties. Probabilistic martingales can simulate the "betting games" and can cover the same class that a "natural proof" diagonalizes against, as implicitly already shown. The notion would become a full-fledged measure on bounded-error complexity classes such as BPP and BPE if it could be shown to satisfy the "measure conservation" axiom for these classes. We give a sufficient condition in terms of simulation by "decisive" probabilistic martingales that implies not only measure conservation, but also a much tighter bounded error probabilistic time hierarchy than is currently known. In particular it implies BPTIME[O(n)]/spl ne/BPP, which would stand in contrast to recent claims of an oracle A giving BPTIME/sup A/[O(n)]=BPP/sup A/. This paper also makes new contributions to the problem of defining (deterministic) measure on P and other sub-exponential classes.