A note on relativizing complexity classes with tally
HEMACHANDRA L. A., Roy S. Rubinstein · 2002
T. Long and A. 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. For relativized worlds, it is shown in this work that even for such pairs of classes, collapsing the classes with a tally oracle is easier than truly collapsing the classes, and it is demonstrated 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.>