ECCC-Report TR10-055https://eccc.weizmann.ac.il/report/2010/055Comments and Revisions published for TR10-055en-usSat, 30 Oct 2010 13:05:03 +0200
Revision 2
| Avoiding Simplicity is Complex |
Eric Allender,
Holger Spakowski
https://eccc.weizmann.ac.il/report/2010/055#revision2It 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.
Sat, 30 Oct 2010 13:05:03 +0200https://eccc.weizmann.ac.il/report/2010/055#revision2
Revision 1
| Avoiding Simplicity is Complex |
Eric Allender
https://eccc.weizmann.ac.il/report/2010/055#revision1It 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.
Tue, 04 May 2010 05:54:47 +0300https://eccc.weizmann.ac.il/report/2010/055#revision1
Paper TR10-055
| Avoiding Simplicity is Complex |
Eric Allender
https://eccc.weizmann.ac.il/report/2010/055It 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.
Wed, 31 Mar 2010 10:02:03 +0300https://eccc.weizmann.ac.il/report/2010/055