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