archives

The Quantitative Structure of Exponential Tim


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

Lutz, Jack H. (1996) The Quantitative Structure of Exponential Tim. Technical Report TR96-08, Department of Computer Science, Iowa State University.

Full text available as:Postscript
Adobe PDF

Abstract

The Quantitative Structure of Exponential Time
Jack H. Lutz
Department of Computer Science
Iowa State University
Ames, Iowa   50010
Recent results on the internal, measure-theoretic structure of the
exponential time complexity classes
linear                  polynomial
E = DTIME(2      ) and E  = DTIME(2          )
2
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:00000128
Deposited by:Staff Account on 30 September 1996



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