2015/11/19 by Gwen Spencer, David Rolnick, Spencer, Gwen +1
Computer Science · #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #Formal Methods in Verification #Polynomial and algebraic computation #Symbolic Computation (cs.SC)
paper · pdf · doi:10.48550/arxiv.1511.06436
openalex publication_date 2015/11/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The computation of Gröbner bases is an established hard problem. By contrast with many other problems, however, there has been little investigation of whether this hardness is robust. In this paper, we frame and present results on the problem of approximate computation of Gröbner bases. We show that it is NP-hard to construct a Gröbner basis of the ideal generated by a set of polynomials, even when the algorithm is allowed to discard a (1 - ε) fraction of the generators, and likewise when the algorithm is allowed to discard variables (and the generators containing them). Our results shows that computation of Gröbner bases is robustly hard even for simple polynomial systems (e.g. maximum degree 2, with at most 3 variables per generator). We conclude by greatly strengthening results for the Strong c-Partial Gröbner problem posed by De Loera et al. Our proofs also establish interesting connections between the robust hardness of Gröbner bases and that of SAT variants and graph-coloring.