loading...
NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly
June 22-June 26
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2008.212008 IEEE 23rd Annual Conference on C ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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
Usage of this product signifies your acceptance of the Terms of Use.