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.
Kolmogorov Complexity, Complexity Cores, and the Distribution of Hardness
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.
Contact site administrator at: firstname.lastname@example.org