Number of the records: 1
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
- 1.
SYSNO ASEP 0352607 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory Author(s) Allender, E. (US)
Koucký, Michal (MU-W) RID, SAI, ORCID
Ronneburger, D. (US)
Roy, S. (IN)Source Title Journal of Computer and System Sciences. - : Elsevier - ISSN 0022-0000
Roč. 77, č. 1 (2011), s. 14-40Number of pages 27 s. Language eng - English Country US - United States Keywords Circuit complexity ; Distinguishing complexity ; FewEXP ; Formula size ; Kolmogorov complexity Subject RIV BA - General Mathematics R&D Projects GAP202/10/0854 GA ČR - Czech Science Foundation (CSF) 1M0545 GA MŠMT - Ministry of Education, Youth and Sports (MEYS) IAA100190902 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR) CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000284450000003 EID SCOPUS 78349310875 DOI 10.1016/j.jcss.2010.06.004 Annotation 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2011
Number of the records: 1