Počet záznamů: 1
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
0352607 - MU-W 2011 RIV US eng J - Článek v odborném periodiku
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
Grant CEP: GA ČR GAP202/10/0854; GA MŠk(CZ) 1M0545; GA AV ČR IAA100190902
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: Circuit complexity * Distinguishing complexity * FewEXP * Formula size * Kolmogorov complexity
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 1.157, rok: 2011
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.
Trvalý link: http://hdl.handle.net/11104/0192081
Název souboru Staženo Velikost Komentář Verze Přístup Koucky.pdf 1 404.2 KB Vydavatelský postprint vyžádat