The Complexity and Distribution of Hard Problems

Measure-theoretic aspects of the polynomial-time many-one reducibility structure of the exponential time complexity classes E=DTIME(2^linear) and E2=DTIME(2^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 polynomial-time many-one 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 bounds say that the polynomial-time many-one 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 polynomial-time many-one complete languages for E form a measure 0 subset of E (and similarly in E2). This latter fact is seen to be a special case of a more general theorem, namely, that every polynomial-time many-one degree (e.g., the degree of all polynomial-time many-one complete languages for NP) has measure 0 in E and in E2