archives

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