Lutz, Jack H. (1990) A Pseudorandum Oracle Characterization of BBP. Technical Report TR90-04, 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: email@example.com