2008
NP-hard sets are exponentially dense unless coNP C NP/poly
Publication
Publication
Presented at the
IEEE Conference on Computational Complexity
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.
Additional Metadata | |
---|---|
, , | |
IEEE Computer Society | |
Quantum Information Processing | |
IEEE Conference on Computational Complexity | |
Organisation | 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. |