Complexity of Gröbner basis detection and border basis detection
type: Item
instance of: scholarly article
title: Complexity of Gröbner basis detection and border basis detection
zbMATH Open document ID: 1258.13029
author: Prabhanjan Ananth
author: Ambedkar Dukkipati
published in: Theoretical Computer Science
publication date: 2012-11-08T00:00:00Z
review text: The authors introduce the border basis detection problem (BBD) which is to decide if a given set of polynomials is a border basis with respect to some order ideal. A similar problem is the Gröbner basis detection problem (GBD) which is to decide if a set of polynomials is a Gröbner basis with respect to some term order. GBD was shown to be NP-hard by \textit{B. Sturmfels} and \textit{M. Wiegelmann} [Appl. Algebra Eng. Commun. Comput. 8, No. 4, 257-263 (1997; Zbl 1055.13503)]. In the present paper the authors show that BBD is NP-complete, that is, NP-hard and NP itself, by relating it to the 3,4-SAT problem.
reviewed by: Thomas Kahle
Mathematics Subject Classification ID: 13P10
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 6103618
zbMATH Keywords: Gröbner bases
zbMATH Keywords: Border bases
zbMATH Keywords: Complexity
zbMATH Keywords: NP problems
MaRDI profile type: Publication
full work available at URL: j.tcs.2012.08.002
OpenAlex ID: W2048364901
cites work: Lifting standard bases in filtered structures
cites work: Border basis detection is NP-complete
cites work: Q3806684
cites work: Computing Gröbner bases by FGLM techniques in a non-commutative setting
cites work: A Polyhedral Characterization of Border Bases
cites work: Bruno Buchberger's PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. Translation from the German
cites work: A new efficient algorithm for computing Gröbner bases \((F_4)\)
cites work: Q4660688
cites work: Advances in Cryptology - CRYPTO 2003
cites work: A new incremental algorithm for computing Groebner bases
cites work: Q4198056
cites work: Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
cites work: A superexponential lower bound for Gröbner bases and Church-Rosser commutative thue systems
cites work: Characterizations of border bases
cites work: Computing border bases
cites work: Q5505187
cites work: Q4507801
cites work: Membership in polynomial ideals over Q is exponential space complete
cites work: Q4502650
cites work: Generalized normal forms and polynomial system solving
cites work: Stable normal forms for polynomial system solving
cites work: Structural Gröbner basis detection
cites work: A simplified NP-complete satisfiability problem
DOI: 10.1016/J.TCS.2012.08.002
description: scientific article; zbMATH DE number 6103618