The complexity of computing the Hilbert polynomial of smooth equidimensional complex projective varieties

DOI10.1007/S10208-005-0175-0MaRDI QIDQ870482zbMATH OpenOpenAlexFDO

Authors Peter Bürgisser, Martin Lotz

Publication date 12 March 2007

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0502044

zbMATH Keywords

counting complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Classical problems, Schubert calculus (14N15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Abstract: 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).

Recommendations

• On the complexity of counting components of algebraic varieties
• On numerical invariants in algebraic complexity theory
• Polynomial complexity for Hilbert series of Borel type ideals
• Computation of Hilbert functions
• Sheaf cohomology is \(\#\)P-hard

Cited in

(12)

• Degeneracy loci and polynomial equation solving
• Polar varieties revisited
• Castelnuovo-Mumford regularity and computing the de Rham cohomology of smooth projective varieties
• On the complexity of smooth projective toric varieties
• The bottleneck degree of algebraic varieties
• On numerical invariants in algebraic complexity theory
• Numerical polar calculus and cohomology of line bundles
• On the complexity of counting components of algebraic varieties
• Local polar varieties in the geometric study of singularities
• The complexity to compute the Euler characteristic of complex varieties
• Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
• Computational aspects of equivariant Hilbert series of canonical rings for algebraic curves

This page was built for publication: The complexity of computing the Hilbert polynomial of smooth equidimensional complex projective varieties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q870482)