A Note on Relativizing Complexity Classes with Tally Oracles
Lane A. Hemachandra, Roy S. Rubinstein · Structure in Complexity Theory Annual Conference · 1990
Long and Selman proved that, for most familiar pairs of complexity classes, separating the classes with a tally oracle is no easier than truly separating the classes. In relativized worlds, (1) we show that even for such pairs of classes, collapsing the classes with a tally oracle is easier than truly collapsing the classes, and (2) refuting a claim in the literature, we demonstrate for the first time that for many familiar pairs of complexity classes, separating the classes with a tally oracle is easier than truly separating the classes.