The Complexity and Distribution of Hard Problems

Juedes, David W. and Lutz, Jack H. (1992) The Complexity and Distribution of Hard Problems. Technical Report TR92-23, Department of Computer Science, Iowa State University.

Abstract

The Complexity and Distribution
of Hard Problems
David W. Juedes and Jack H. Lutz
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.


Subjects:
All uncategorized technical reports


ID code:
00000026
Deposited by:
Staff Account on 13 August 1992





Contact site administrator at: ssg@cs.iastate.edu