archives

A Pseudorandum Oracle Characterization of BBP


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

Lutz, Jack H. (1990) A Pseudorandum Oracle Characterization of BBP. Technical Report TR90-04, 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:00000003
Deposited by:Staff Account on 01 April 1990



Contact site administrator at: ssg@cs.iastate.edu