2008 · 30 citations · 9 references
ComputingComputer ScienceMathematicsDiscrete MathematicsSet TheoryTheory Of ComputationComplexity TheoryComputability TheoryComputational ComplexityComputational Complexity ClassesCompleteness ResultsExponential Time ComplexityNp-complete ProblemsNp-completenessNp-hardnessPolynomial HierarchyPolynomial-time Reductions
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.
9
Some connections between nonuniform and uniform complexity classes
Richard M. Karp, Richard J. Lipton · 1980 · 582 citations · Full text
On Isomorphisms and Density of $NP$ and Other Complete Sets
L. Berman, Juris Hartmanis · SIAM Journal on Computing · 1977 · 460 citations
Some consequences of non-uniform conditions on uniform classes
Chee Yap · Theoretical Computer Science · 1983 · 243 citations