Complexity of Gröbner basis detection and border basis detection (Q1758159)

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.