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.
Index Terms:
hard sets, polynomial advice, instance complexity
Citation:
Harry Buhrman, John M. Hitchcock, "NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly," ccc, pp.1-7, 2008 IEEE 23rd Annual Conference on Computational Complexity, 2008