%0 Journal Article
%T On the robust hardness of Gr£¿bner basis computation
%A Gwen Spencer
%A David Rolnick
%J Computer Science
%D 2015
%I arXiv
%X 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.
%U http://arxiv.org/abs/1511.06436v1