Separating complexity classes with tally oracles
Lane A. Hemaspaandra, Roy S. Rubinstein · Theoretical Computer Science · 1992
Long and Selman (1986) proved that, for most familiar pairs of complexity classes, separating the classes with a tally oracle is no easier than truly separating the classes. Refuting a claim in the literature, we prove 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.