Kolmogorv Complexity, Complexity Cores, and the Distribution of Hardness
|
Home About Browse Search Register Subscriptions Deposit Papers Help |
Juedes, David W. and Lutz, Jack H. (1991) Kolmogorv Complexity, Complexity Cores, and the Distribution of Hardness. Technical Report TR91-09a, Department of Computer Science, Iowa State University.
| Full text available as: | Postscript Adobe PDF |
Abstract
Kolmogorov Complexity, Complexity Cores, and the Distribution of Hardness by David W. Juedes and Jack H. Lutz Every language that is polynomial time many-one hard for ESPACE is shown to have unusually small complexity cores and unusually low space-bounded Kolmogorov complexity. It follows that the polynomial time many-one complete languages form a measure 0 subset of ESPACE.
| Subjects: | All uncategorized technical reports |
| ID code: | 00000006 |
| Deposited by: | Staff Account on 01 April 1991 |
Contact site administrator at: ssg@cs.iastate.edu