Avoiding Simplicity is Complex.
Eric Allender · 2010
Abstract. 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? 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) ≥ KNt(x); the two measures are polynomially related if and only if NEXP ⊆ EXP/poly [5]. 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 instance, EXP = ZPP if and only if there is a “dense ” set in P (i.e., a set that contains at least 2 n /n k strings of each length n, forsomek) that contains no strings x of length n with Kt(x) ≤ n ɛ,forsomeɛ>0 [4]. That is, the EXP vs ZPP question is equivalent to (one version of) the question of whether avoiding simple strings is difficult. Surprisingly, we are able to show unconditionally that avoiding simple strings (in the sense of KNt complexity) is difficult. Every dense set in NP ∩ co-NP contains infinitely many strings x such that KNt(x) ≤|x | ɛ for some ɛ. 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. 1