Scholarlink

<p>Mayr and Meyer considered the <i>ideal membership problem</i> and showed that it is <span>Expspace hard</span>. In order to prove the hardness result, Mayr and Meyer introduced a class of polynomials that can exactly count double exponential value. This set of polynomials were later used by Huynh to show hardness for reduced Gröbner basis and by Bayer and Stillman to show hardness for syzygy. In this article, we will present these results along with the proof ideas involved, in a simplified form. In particular, our proofs for hardness of Gröbner basis and syzygy are different from the existing proofs.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Hardness for Gröbner basis, Syzygy and ideal membership problem

  • 期刊论文

  • 发表日期：

    2026年1月7日

查看全文
  • Archana S Morye,
  • Sreenanda S B,
  • Prakash Saivasan

摘要

Mayr and Meyer considered the ideal membership problem and showed that it is Expspace hard. In order to prove the hardness result, Mayr and Meyer introduced a class of polynomials that can exactly count double exponential value. This set of polynomials were later used by Huynh to show hardness for reduced Gröbner basis and by Bayer and Stillman to show hardness for syzygy. In this article, we will present these results along with the proof ideas involved, in a simplified form. In particular, our proofs for hardness of Gröbner basis and syzygy are different from the existing proofs.