Sparse Complete Sets for NP: Solution of a Conjecture by Berman and Hartmanis
Mahaney, Stephen R.
In this paper we show that if NP has a sparse complete set under many-one reductions, then P=NP. The result is extended to show that if NP is sparse reducible, then P=NP. The main techniques of this paper generalize the NP recognizer for the complement of a sparse complete set with census function to the case where the census function is not known (c.f. [HM]), then a many-one reduction of this language to the sparse set permits a polynomial time bounded tree search as in [B], [F], or [MP]. Even without actual knowledge of the census, the algorithm utilizes the properties of the true census to decide membership in SAT in polynomial time.
computer science; technical report
Previously Published As