NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly

Harry Buhrman, John M. Hitchcock

2008 · 30 citations · 9 references

DOIFull text

Open access

Concepts

Abstract

We show that hard sets S for NP must have exponential density, i.e. |S <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">=n</sub> | ges 2n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">epsi</sup> for some isin > 0 and infinitely many n, unless coNP sube NP/poly and the polynomial-time hierarchy collapses. This result holds for Turing reductions that make n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1-isin</sup> queries. In addition we study the instance complexity o/NP- hard problems and show that hard sets also have an exponential amount of instances that have instance complexity n for some sigma > 0. This result also holds for Turing reductions that make n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1-isin</sup> queries.

References

9