Lutz, Jack H. (1996) The Quantitative Structure of Exponential Tim. Technical Report TR96-08, Department of Computer Science, Iowa State University.
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
E = DTIME(2 ) and E = DTIME(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.
Contact site administrator at: email@example.com