A Pseudorandum Oracle Characterization of BBP
Jack H. Lutz · Iowa State University Digital Repository (Iowa State University) · 1990
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.