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