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

Peter Burgisser; Martin Lotz

doi:10.1007/s10208-005-0175-0

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

Peter Burgisser
, Martin Lotz

Department of Mathematics

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

8 Citations (Scopus)

Abstract

We continue the study of counting complexity begun in [13], [14], [15] 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. The reduction is based on a new formula for the coefficients of the Hilbert polynomial of a smooth variety. 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 in Bach [1]. © 2005 Society for the Foundations of Computational Mathematics.

Original language	English
Pages (from-to)	59-86
Journal	Foundations of Computational Mathematics
Volume	7
Issue number	1
DOIs	https://doi.org/10.1007/s10208-005-0175-0
Publication status	Published - Feb 2007

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Funding

Both authors were partially supported by DFG grant BU 1371 and the Paderborn Institute for Scientific Computation (PaSCo). We thank Felipe Cucker for discussions and for inviting us to Hong Kong in Spring 2004, where the basis of this work was elaborated in the joint papers [14], [15].

Access Output

10.1007/s10208-005-0175-0

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{5bc42953d6f544ca8c4ffeba14ef48ec,

title = "The complexity of computing the hilbert polynomial of smooth equidimensional complex projective varieties",

abstract = "We continue the study of counting complexity begun in [13], [14], [15] 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. The reduction is based on a new formula for the coefficients of the Hilbert polynomial of a smooth variety. 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 in Bach [1]. {\textcopyright} 2005 Society for the Foundations of Computational Mathematics.",

author = "Peter Burgisser and Martin Lotz",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].",

year = "2007",

month = feb,

doi = "10.1007/s10208-005-0175-0",

language = "English",

volume = "7",

pages = "59--86",

journal = "Foundations of Computational Mathematics",

issn = "1615-3375",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - The complexity of computing the hilbert polynomial of smooth equidimensional complex projective varieties

AU - Burgisser, Peter

AU - Lotz, Martin

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 2007/2

Y1 - 2007/2

N2 - We continue the study of counting complexity begun in [13], [14], [15] 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. The reduction is based on a new formula for the coefficients of the Hilbert polynomial of a smooth variety. 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 in Bach [1]. © 2005 Society for the Foundations of Computational Mathematics.

AB - We continue the study of counting complexity begun in [13], [14], [15] 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. The reduction is based on a new formula for the coefficients of the Hilbert polynomial of a smooth variety. 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 in Bach [1]. © 2005 Society for the Foundations of Computational Mathematics.

UR - https://www.scopus.com/pages/publications/33846897800

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-33846897800&origin=recordpage

U2 - 10.1007/s10208-005-0175-0

DO - 10.1007/s10208-005-0175-0

M3 - RGC 21 - Publication in refereed journal

SN - 1615-3375

VL - 7

SP - 59

EP - 86

JO - Foundations of Computational Mathematics

JF - Foundations of Computational Mathematics

IS - 1

ER -

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

Abstract

Bibliographical note

Funding

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this