The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory

0352607 - MÚ 2011 RIV US eng J - Journal Article
Allender, E. - Koucký, Michal - Ronneburger, D. - Roy, S.
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory.
Journal of Computer and System Sciences. Roč. 77, č. 1 (2011), s. 14-40. ISSN 0022-0000. E-ISSN 1090-2724
R&D Projects: GA ČR GAP202/10/0854; GA MŠMT(CZ) 1M0545; GA AV ČR IAA100190902
Institutional research plan: CEZ:AV0Z10190503
Keywords : Circuit complexity * Distinguishing complexity * FewEXP * Formula size * Kolmogorov complexity
Subject RIV: BA - General Mathematics
Impact factor: 1.157, year: 2011
http://www.sciencedirect.com/science/article/pii/S0022000010000887

We continue an investigation into resource-bounded Kolmogorov complexity, which highlights the close connections between circuit complexity and Levin's time-bounded Kolmogorov complexity measure Kt (and other measures with a similar flavor), and also exploits derandomization techniques to provide new insights regarding Kolmogorov complexity. The Kolmogorov measures that have been introduced have many advantages over other approaches to defining resource-bounded Kolmogorov complexity. Here, we study the properties of other measures that arise naturally in this framework.The motivation for introducing yet more notions of resource-bounded Kolmogorov complexity are two-fold: 1) to demonstrate that other complexity measures such as branching-program size and formula size can also be discussed in terms of Kolmogorov complexity, and 2) to demonstrate that notions such as nondeterministic Kolmogorov complexity and distinguishing complexity also fit well into this framework.
Permanent Link: http://hdl.handle.net/11104/0192081