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.