ECCC-Report TR04-015https://eccc.weizmann.ac.il/report/2004/015Comments and Revisions published for TR04-015en-usWed, 25 Feb 2004 08:52:23 +0200
Paper TR04-015
| Enumerations of the Kolmogorov Function |
Richard Beigel,
Harry Buhrman,
Peter Fejer,
Lance Fortnow,
Piotr Grabowski,
Luc Longpré,
Andrej Muchnik,
Frank Stephan,
Leen Torenvliet
https://eccc.weizmann.ac.il/report/2004/015A recursive enumerator for a function $h$ is an algorithm $f$ which
enumerates for an input $x$ finitely many elements including $h(x)$.
$f$ is an $k(n)$-enumerator if for every input $x$ of length $n$, $h(x)$
is among the first $k(n)$ elements enumerated by $f$.
If there is a $k(n)$-enumerator for $h$
then $h$ is called $k(n)$-enumerable.
We also consider enumerators which are only $A$-recursive for some
oracle~$A$.
We determine exactly how hard it is to enumerate the Kolmogorov
function, which assigns to each string $x$ its Kolmogorov complexity:
For every underlying universal machine $U$, there is a constant $a$
such that $C$ is $k(n)$-enumerable only if $k(n) \geq n/a$ for almost
all $n$.
For any given constant $k$, the Kolmogorov function is
$k$-enumerable relative to an oracle $A$
if and only if $A$ is at least as hard as the halting problem.
There exists an r.e., Turing-incomplete set $A$ such for
every non-decreasing and unbounded recursive function $k$,
the Kolmogorov function is $k(n)$-enumerable relative to $A$.
The last result is obtained by using a relativizable construction
for a nonrecursive set $A$ relative to which the prefix-free
Kolmogorov complexity differs only by a constant from the unrelativized
prefix-free Komogorov complexity.
Although every $2$-enumerator for $C$ is Turing hard for $K$, we
show that reductions must depend on the specific choice of the
$2$-enumerator and there is no bound on the quantity of their
queries. We show our negative results even for strong $2$-enumerators
as an oracle where the querying machine for any $x$ gets directly
an explicit list of all hypotheses of the enumerator for this input.
The limitations are very general and we show them
for any recursively bounded function $g$.
For every Turing reduction $M$ and every non-recursive set $B$,
there is a strong $2$-enumerator $f$ for $g$ such that $M$ does not
Turing reduce $B$ to $f$.
For every non-recursive set $B$, there is a strong $2$-enumerator $f$
for $g$ such that $B$ is not wtt-reducible to $f$.
Furthermore, we deal with the resource-bounded case and give
characterizations for the class SymP introduced by Russell and
Sundaram and the classes PSPACE, EXP.
SymP is the class of all sets $A$ for which there is a
polynomially bounded function $g$ such that there is one
tt-reduction which reduces $A$ to every strong $2$-enumerator
for $g$.
PSPACE is the class of all sets $A$ for which there is a
polynomially bounded function $g$ such that there is one
Turing reduction which reduces $A$ to every strong $2$-enumerator
for $g$. Interestingly, $g$ can be taken to be the Kolmogorov
function for the conditional space-bounded Kolmogorov complexity.
EXP is the class of all sets $A$ for which there is a
polynomially bounded function $g$ and a machine $M$ which
witnesses $A$ $\in$ PSPACE$^f$ for all strong $2$-enumerators
$f$ for $g$.
Finally, we show that any strong $O(\log n)$-enumerator for
the conditional space-bounded Kolmogorov function must be
PSPACE-hard if P = NP.
Wed, 25 Feb 2004 08:52:23 +0200https://eccc.weizmann.ac.il/report/2004/015