ECCC-Report TR08-022https://eccc.weizmann.ac.il/report/2008/022Comments and Revisions published for TR08-022en-usTue, 11 Mar 2008 07:16:02 +0200
Paper TR08-022
| NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly |
Harry Buhrman,
John Hitchcock
https://eccc.weizmann.ac.il/report/2008/022We show that hard sets S for NP must have exponential density, i.e. |S<sub>=n</sub>| &#8805; 2<sup>n<sup>&#949;</sup></sup> for some &#949; > 0 and infinitely many n, unless coNP &#8838; NP\poly and the polynomial-time hierarchy collapses. This result holds for Turing reductions that make n<sup>1-&#949;</sup> 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<sup>&#948;</sup> for some &#948; > 0. This result also holds for Turing reductions that make n<sup>1-&#949;</sup> queries.
Tue, 11 Mar 2008 07:16:02 +0200https://eccc.weizmann.ac.il/report/2008/022