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 a 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:
[start-list]
*
For every underlying universal machine U, there is a constant a
such that C is k(n)-enumerable only if k(n) ≥ 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.[end-list]
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 Kolmogorov 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:
[start-list]
*
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.[end-list]
Furthermore, we deal with the resource-bounded case and give
characterizations for the class S₂p introduced by Canetti and
independently Russell and Sundaram and the classes PSPACE,
EXP.
[start-list]
*
S₂p is the class of all sets A for which there is
a polynomially bounded function g such that there is
a polynomial time 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
a polynomial time 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 ∈ PSPACEf for all strong 2-enumerators
f for g.[end-list]