首页> 外文期刊>Foundations of Computational Mathematics >The Complexity of Computing the Hilbert Polynomial of Smooth Equidimensional Complex Projective Varieties
【24h】

The Complexity of Computing the Hilbert Polynomial of Smooth Equidimensional Complex Projective Varieties

机译:计算光滑等维复投影变种的希尔伯特多项式的复杂度

获取原文
获取原文并翻译 | 示例

摘要

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].
机译:我们通过证明计算齐次理想的希尔伯特多项式的复杂度的上限和下限,继续[13],[14],[15]中开始的复杂度计数研究。我们表明,计算光滑等维复射影变种的希尔伯特多项式的问题可以在多项式时间内减少到对有限多元多项式的复杂复零数目进行计数的问题上。归约基于平滑变种的希尔伯特多项式系数的新公式。此外,我们证明了计算齐次理想的希尔伯特多项式的更普遍的问题是多项式空间难。这意味着对于投影空间上相干绳轮的同调滑轮组的秩和欧拉特征的计算和多项式问题,多项式空间下界均得到改善,从而改善了Bach [1]中的#P下界。

著录项

  • 来源
    《Foundations of Computational Mathematics》 |2007年第1期|59-86|共28页
  • 作者

    Peter Burgisser; Martin Lotz;

  • 作者单位

    Institute of Mathematics University of Paderborn D-33095 Paderborn Germany;

    Department of Mathematics City University of Hong Kong 83 Tat Chee Avenue Kowloon Hong Kong;

  • 收录信息
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号