The Complexity and Distribution of Hard Problems

Abstract

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$.