Separating complexity classes using autoreducibility

Harry Buhrman, Lance Fortnow, Leen Torenvliet +1

A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hie…