A note on sparse oracles for NP

摘要

We prove that if S is a sparse oracle for NP, then S is a sparse oracle for the polynomialtime hierarchy. Consequently, if NP has either a sparse or co-sparse ⩽TP-complete set, then the polynomial-time hierarchy collapses to Δ2P.. S. Mahaney (Proceedings, 21st IEEE Symposium, Foundations of Computer Science, 1980) had previously shown that if NP has a sparse ⩽TP-complete set, then the polynomial-time hierarchy collapses to Δ2P. Our single construction yields Mahaney's result for sparse ⩽TP-complete sets for NP and also the corresponding result for co-sparse ⩽TP-complete sets for NP. Both results strengthen the earlier work of Karp, Lipton, and Sipser, Proceedings, Twelfth ACM Symposium Theory of Computing, 1980, who proved that if NP has a sparse ⩽TP-complete set, then the polynomial-time hierarchy collapses to Σ2P ∩ Π2P .