archives

The Quantitative Structure of Exponential Time


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

Lutz, Jack H. (1993) The Quantitative Structure of Exponential Time. Technical Report TR93-14, Department of Computer Science, Iowa State University.

Full text available as:Postscript
Adobe PDF

Abstract

The Quantitative Structure of Exponential Time
by
Jack H. Lutz
Recent results on the internal, measure-theoretic structure of the
exponential time complexity classes E = DTIME(2^linear) and E2 =
DTIME(2^polynomial) are surveyed.  The measure structure of these
classes is seen to interact in informative ways with bi-immunity,
complexity cores, polynomial-time many-one reducibility, circuit-size
complexity, Kolmogorov complexity, and the density of hard languages.
Possible implications for the structure of NP are also discussed.

Subjects:All uncategorized technical reports
ID code:00000050
Deposited by:Staff Account on 22 December 1993



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