Lutz, Jack H. (1993) The Quantitative Structure of Exponential Time. Technical Report TR93-14, Department of Computer Science, Iowa State University.
The Quantitative Structure of Exponential Time
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.
Contact site administrator at: email@example.com