archives

Kolmagorav Complexity, Complexity Cores, and the Distribution of Hardness


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

Juedes, David W. and Lutz, Jack H. (1992) Kolmagorav Complexity, Complexity Cores, and the Distribution of Hardness. Technical Report TR92-12, 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
Problems that are complete for exponential space are provably
intractable and known to be exceedingly complex in several
technical respects.  However, every problem decidable in exponential
space is efficiently reducible to every complete problem, so
each complete problem must have a highly organized structure.
The authors have recently exploited this fact to prove that complete
problems are, in two respects, unusually simple for problems in
expontential space.  Specifically, every complete problem must have
unusually small complexity cores and unusually low
space-bounded Kolmogorov complexity.  It follows that the complete
problems form a negligibly small subclass of the problems decidable
in exponential space.  This paper explains the main ideas of this work.

Subjects:All uncategorized technical reports
ID code:00000018
Deposited by:Staff Account on 21 April 1992



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