archives

The Complexity and Distribution of Hard Problems


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

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.

Full text available as:Postscript
Adobe PDF

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