COMPLEXITY OF GRÖBNER BASIS DETECTION AND BORDER BASIS DETECTION

Abstract. Gröbner basis detection (GBD) is defined as follows: given a set of polynomials, decide whether there exists- and if “yes ” find- a term order such that the set of polynomials is a Gröbner basis. This problem was pro-posed by Gritzmann and Sturmfels (1993) and it was shown to be NP-hard by Sturmfels and Wiegelmann. We investigate the computational complex-ity of this problem when the given set of polynomials are the generators of a zero-dimensional ideal. Further, we propose the Border basis detection (BBD) problem which is formulated as follows: given a set of generators of an ideal, decide whether the set of generators is a border basis of the ideal with respect to some order ideal. We analyse the complexity of this problem and prove it to be NP-complete