全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

On the robust hardness of Gr?bner basis computation

Full-Text   Cite this paper   Add to My Lib

Abstract:

We introduce a new problem in the approximate computation of Gr\"{o}bner bases that allows the algorithm to ignore a constant fraction of the generators - of the algorithm's choice - then compute a Gr\"{o}bner basis for the remaining polynomial system. The set ignored is subject to one quite-natural structural constraint. For lexicographic orders, when the discarded fraction is less than $(1/4-\epsilon)$, for $\epsilon>0$, we prove that this problem cannot be solved in polynomial time, even when the original polynomial system has maximum degree 3 and each polynomial contains at most 3 variables. Qualitatively, even for sparse systems composed of low-degree polynomials, we show that Gr\"{o}bner basis computation is robustly hard: even producing a Gr\"{o}bner basis for a large subset of the generators is NP-hard.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133