TR04-015 Authors: Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet

Publication: 25th February 2004 08:52

Downloads: 1973

Keywords:

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.