Počet záznamů: 1

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

  1. 1.
    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
    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.
    Trvalý link: http://hdl.handle.net/11104/0192081
    Název souboruStaženoVelikostKomentářVerzePřístup
    Koucky.pdf1404.2 KBVydavatelský postprintvyžádat