Kolmagorav Complexity, Complexity Cores, and the Distribution of Hardness
Date
Authors
Lutz, Jack
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Journal Issue
Series
Department
Abstract
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.