2016/05/14 by Gwen Spencer, Spencer, Gwen
Computer Science · Mathematics · #Commutative Algebra and Its Applications #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #Polynomial and algebraic computation #Symbolic Computation (cs.SC)
paper · pdf · doi:10.48550/arxiv.1605.04472
openalex publication_date 2016/05/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Two models were recently proposed to explore the robust hardness of Gröbner basis computation. Given a polynomial system, both models allow an algorithm to selectively ignore some of the polynomials: the algorithm is only responsible for returning a Gröbner basis for the ideal generated by the remaining polynomials. For the q-Fractional Gröbner Basis Problem the algorithm is allowed to ignore a constant (1-q)-fraction of the polynomials (subject to one natural structural constraint). Here we prove a new strongest-parameter result: even if the algorithm is allowed to choose a (3/10-ε)-fraction of the polynomials to ignore, and need only compute a Gröbner basis with respect to some lexicographic order for the remaining polynomials, this cannot be accomplished in polynomial time (unless P=NP). This statement holds even if every polynomial has maximum degree 3. Next, we prove the first robust hardness result for polynomial systems of maximum degree 2: for the q-Fractional model a (1/5-ε) fraction of the polynomials may be ignored without losing provable NP-Hardness. Both theorems hold even if every polynomial contains at most three distinct variables. Finally, for the Strong c-partial Gröbner Basis Problem of De Loera et al. we give conditional results that depend on famous (unresolved) conjectures of Khot and Dinur, et al.