
Computer Science 2015
On the robust hardness of Gr？bner basis computationAbstract: 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 quitenatural 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 lowdegree 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 NPhard.
