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.
Kolmogorov Complexity, Complexity Cores, and the Distribution of Hardness
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.
Contact site administrator at: firstname.lastname@example.org