科研之友
微信
新浪微博
Facebook
分享链接
摘要
It is a trivial observation that every decidable set has strings of length n with Kolmogorov complexity log n + O(1) if it has any strings of length n at all. Things become much more interesting when one asks whether a similar property holds when one considers resource-bounded Kolmogorov complexity. This is the question considered here: Can a feasible set A avoid accepting strings of low resource-bounded Kolmogorov complexity, while still accepting some (or many) strings of length n? %26lt;br%26gt;More specifically, this paper deals with two notions of resource-bounded Kolmogorov complexity: Kt and KNt. The measure Kt was defined by Levin more than three decades ago and has been studied extensively since then. The measure KNt is a nondeterministic analog of Kt. For all strings x, Kt(x) %26gt;= KNt(x); the two measures are polynomially related if and only if NEXP subset of EXP/poly (Allender et al. in J. Comput. Syst. Sci. 77:14-40, 2011). %26lt;br%26gt;Many longstanding open questions in complexity theory boil down to the question of whether there are sets in P that avoid all strings of low Kt complexity. For example, the EXP vs ZPP question is equivalent to (one version of) the question of whether avoiding simple strings is difficult: (EXP = ZPP if and only if there exist epsilon %26gt; 0 and a %26quot;dense%26quot; set in P having no strings x with Kt(x) %26lt;= vertical bar x vertical bar(epsilon) (Allender et al. in SIAM J. Comput. 35:1467-1493, 2006)). %26lt;br%26gt;Surprisingly, we are able to show unconditionally that avoiding simple strings (in the sense of KNt complexity) is difficult. Every dense set in NP boolean AND coNP contains infinitely many strings x such that KNt(x) %26lt;= vertical bar x vertical bar(epsilon) for every epsilon %26gt; 0. The proof does not relativize. As an application, we are able to show that if E = NE, then accepting paths for nondeterministic exponential time machines can be found somewhat more quickly than the brute-force upper bound, if there are many accepting paths.
- 出版日期2012-10
