Počet záznamů: 1
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
- 1.
SYSNO ASEP 0352607 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory Tvůrce(i) Allender, E. (US)
Koucký, Michal (MU-W) RID, SAI, ORCID
Ronneburger, D. (US)
Roy, S. (IN)Zdroj.dok. Journal of Computer and System Sciences. - : Elsevier - ISSN 0022-0000
Roč. 77, č. 1 (2011), s. 14-40Poč.str. 27 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova Circuit complexity ; Distinguishing complexity ; FewEXP ; Formula size ; Kolmogorov complexity Vědní obor RIV BA - Obecná matematika CEP GAP202/10/0854 GA ČR - Grantová agentura ČR 1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy IAA100190902 GA AV ČR - Akademie věd CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000284450000003 EID SCOPUS 78349310875 DOI 10.1016/j.jcss.2010.06.004 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2011
Počet záznamů: 1