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