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.