

Juedes, David W. and Lutz, Jack H. (1992) Kolmagorav Complexity, Complexity Cores, and the Distribution of Hardness. Technical Report TR9212, Department of Computer Science, Iowa State University.
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
spacebounded 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: ssg@cs.iastate.edu
