Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis

摘要

A set S ⊂ Σ∗ is sparse if there is a polynomial p such that the number of strings in S of length at most n is at most p(n). All known NP-complete sets, such as SAT, are polynomial-time isomorphic and are not sparse. The main result of this paper is that if there is a sparse NP-complete set under polynomial-time many-one reductions, then P = NP. We also show that if there is a sparse NP-complete set under polynomial-time Turing reductions, then the polynomial-time hierarchy collapses to Δ2P.