We show that hard sets $S$ for $\NP$ must have exponential density, i.e. $|S_{=n}| \geq 2^{n^\epsilon}$ for some $\epsilon > 0$ and infinitely many $n$, unless $\coNP \subseteq \NP/\poly$ and the polynomial-time hierarchy collapses. This result holds for Turing reductions that make $n^{1-\epsilon}$ queries. In addition we study the instance complexity of $\NP$-hard problems and show that hard sets also have an exponential amount of instances that have instance complexity $n^\delta$ for some $\delta>0$. This result also holds for Turing reductions that make $n^{1-\epsilon}$ queries.

, ,
IEEE Computer Society
Quantum Information Processing
IEEE Conference on Computational Complexity
Quantum Computing and Advanced System Research

Buhrman, H., & Hitchcock, J. (2008). NP-hard sets are exponentially dense unless coNP C NP/poly. IEEE Computer Society.