SIAM Journal on Computing · 1995 · 65 citations · 15 references
ComputingComputer ScienceMathematicsAlgorithmsProbability TheoryTheory Of ComputationAlgorithmic ComplexityComplexity TheoryComputational ComplexityComputational Complexity ClassesStructural ComplexityTime ComplexityComplexity ClassesComplexity-theoretic HardnessComputational Complexity Of LanguagesExponential Time ComplexityLower BoundsPolynomial Time ComplexityReducibilityTuring Reducibility
Measure-theoretic aspects of the $\leq _{\text{m}}^{\text{P}}$-reducibility structure of the exponential time complexity classes ${\text{E}} = {\text{DTIME}}(2^{{\text{linear}}} )$ and ${\text{E}}_2 = {\text{DTIME}}(2^{{\text{polynomial}}} )$ are investigated. Particular attention is given to the complexity (measured by the size of complexity cores) and distribution (abundance in the sense of measure) of languages that are $\leq _{\text{m}}^{\text{P}}$-hard for E and other complexity classes. Tight upper and lower bounds on the size of complexity cores of hard languages are derived. The upper bound says that the $\leq _{\text{m}}^{\text{P}}$-hard languages for E are unusually simple, in the sense that they have smaller complexity cores than most languages in E. It follows that the $\leq _{\text{m}}^{\text{P}}$-complete languages for E form a measure 0 subset of E (and similarly in ${\text{E}}_2$). This latter fact is seen to be a special case of a more general theorem, namely, that every$\leq _{\text{m}}^{\text{P}}$-degree (e.g., the degree of all $\leq _{\text{m}}^{\text{P}}$-complete languages for NP) has measure 0 in E and in ${\text{E}}_2$.
15
On Isomorphisms and Density of $NP$ and Other Complete Sets
L. Berman, Juris Hartmanis · SIAM Journal on Computing · 1977 · 460 citations
Almost everywhere high nonuniform complexity
Jack H. Lutz · Journal of Computer and System Sciences · 1992 · 260 citations
Bi-immune sets for complexity classes
José L. Balcázar, Uwe Schöning · Theory of Computing Systems · 1985 · 119 citations