Relativizing complexity classes with sparse oracles
Timothy J. Long, Alan L. Selman · Journal of the ACM · 1986
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.