Title: The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory.
Abstract: We continue an investigation into resource-bounded Kolmogorov complexity (Allender et al., 2006 [4]), 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 (such as much greater independence from the underlying choice of universal machine that is used to define the measure) (Allender et al., 2006 [4]). 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:*to demonstrate that other complexity measures such as branching-program size and formula size can also be discussed in terms of Kolmogorov complexity, and *to demonstrate that notions such as nondeterministic Kolmogorov complexity and distinguishing complexity (Buhrman et al., 2002 [15]) also fit well into this framework. The main theorems that we provide using this new approach to resource-bounded Kolmogorov complexity are:*A complete set (RKNt) for NEXP/poly defined in terms of strings of high Kolmogorov complexity. *A lower bound, showing that RKNt is not in [email protected]?coNP. *New conditions equivalent to the conditions ''[email protected]?nonuniform NC^1'' and ''[email protected]?L/poly''. *Theorems showing that ''distinguishing complexity'' is closely connected to both FewEXP and to EXP. *Hardness results for the problems of approximating formula size and branching program size.
Publication Year: 2009
Publication Date: 2009-01-01
Language: en
Type: article
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot