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) \geq$ KNt$(x)$; the two measures are polynomially related if and only if NEXP $\subseteq$ EXP/poly.

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 > 0$ and a ``dense'' set in P
having no strings $x$ with Kt$(x) \leq |x|^\epsilon$).

Surprisingly, we are able to show *unconditionally* that avoiding simple strings (in the sense of KNt complexity) is difficult. Every dense set in NP $\cap$ coNP contains infinitely many strings $x$ such that
KNt$(x) \leq |x|^{\epsilon}$ for some $\epsilon$. 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.

There was a bug in the proof of the main result. We can show only that the claim holds for problems in NP intersect coNP -- and not for (NP intersect coNP)/n^{o(1)}. Also, there is a new co-author, and more details about an oracle construction that was merely discussed in the earlier version.

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) \geq$ KNt$(x)$; the two measures are polynomially related if and only if NEXP $\subseteq$ EXP/poly.

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 > 0$ and a ``dense'' set in P
having no strings $x$ with Kt$(x) \leq |x|^\epsilon$).

Surprisingly, we are able to show *unconditionally* that avoiding simple strings (in the sense of KNt complexity) is difficult. Every dense set in NP $\cap$ coNP contains infinitely many strings $x$ such that
KNt$(x) \leq |x|^{\epsilon}$ for some $\epsilon$. 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.

Some relevant work by Impagliazzo, Kabanets, and Wigderson is discussed, and some instances of $|x|^\epsilon$ are replaced by $\epsilon |x|$.

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) \geq$ KNt$(x)$; the two measures are polynomially related if and only if NEXP $\subseteq$ EXP/poly.

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 > 0$ and a ``dense'' set in P
having no strings $x$ with Kt$(x) \leq |x|^\epsilon$).

Surprisingly, we are able to show *unconditionally* that avoiding simple strings (in the sense of KNt complexity) is difficult. Every dense set in NP $\cap$ coNP contains infinitely many strings $x$ such that
KNt$(x) \leq |x|^{\epsilon}$ for some $\epsilon$. 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.