  We continue the study of counting complexity begun in [Buergisser, Cucker 04]
and [Buergisser, Cucker, Lotz 05] by proving upper and lower bounds on the
complexity of computing the Hilbert polynomial of a homogeneous ideal. We show
that the problem of computing the Hilbert polynomial of a smooth
equidimensional complex projective variety can be reduced in polynomial time to
the problem of counting the number of complex common zeros of a finite set of
multivariate polynomials. Moreover, we prove that the more general problem of
computing the Hilbert polynomial of a homogeneous ideal is polynomial space
hard. This implies polynomial space lower bounds for both the problems of
computing the rank and the Euler characteristic of cohomology groups of
coherent sheaves on projective space, improving the #P-lower bound of Bach (JSC
1999).
