ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-015 | 24th February 2004 00:00

Enumerations of the Kolmogorov Function

RSS-Feed

Abstract:

A 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.



ISSN 1433-8092 | Imprint