Avoiding simplicity is complex

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 ques-tion 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 Kol-mogorov 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 [6]. Many longstanding open questions in complexity theory boil down to the ques-tion 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 > 0 and a “dense ” set in P having no strings x with Kt(x) ≤ |x| [5]). Surprisingly, we are able to show unconditionally that avoiding simple strings (in the sense of KNt complexity) is difficult. Every dense set in NP ∩ coNP con-tains infinitely many strings x such that KNt(x) ≤ |x| for every > 0. The proof does not relativize. As an application, we are able to show that if E = NE