Speaker: Eric Allender
Title: 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 question considered in this talk:
Can a feasible set A avoid accepting strings of low resource-bounded
Kolmogorov complexity, while still accepting some (or many) strings of
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 is a subset of 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. As one example, note that the output of a hitting-set
generator is (necessarily) a set of strings having low resource-bounded
Kolmogorov complexity, and thus secure hitting set generators exist if
any "dense" set in P/poly contains strings of small Kt complexity.
As another 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''
P having no strings x with Kt(x)<=
Surprisingly, we are able to show *unconditionally*
that avoiding simple
strings (in the sense of KNt complexity) is difficult. Every dense set
in NP intersect coNP contains infinitely many strings x such that
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. I think that there
should be more interesting applications; perhaps you can find some!
The paper is available here: http://ftp.cs.rutgers.edu/pub/allender/simplicity.pdf