

Juedes, David W. and Lutz, Jack H. (1992) The Complexity and Distribution of Hard Problems. Technical Report TR9223, Department of Computer Science, Iowa State University.
Abstract
The Complexity and Distribution
of Hard Problems
David W. Juedes and Jack H. Lutz
Measuretheoretic aspects of the polynomialtime manyone 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
polynomialtime manyone 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
polynomialtime manyone 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 polynomialtime manyone 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 polynomialtime manyone degree
(e.g., the degree of all polynomialtime manyone complete languages
for NP) has measure 0 in E and in E2.
Contact site administrator at: ssg@cs.iastate.edu
