Relativizing complexity classes with sparse oracles

Abstract

Baker, Gill, and Solovay constructed sparse sets A and B such that P( A ) ≠ NP( A ) and NP( B ) ≠ co-NP( B ). In contrast to their results, we prove that P = NP if and only if for every tally language T , P( T ) = NP( T ), and that NP = co-NP if and only if for every tally language T , NP( T ) = co-NP( T ). We show that the polynomial hierarchy collapses if and only if there is a sparse set S such that the polynomial hierarchy relative to S collapses. Similar results are obtained for several other complexity classes.