Complexity of Gröbner basis detection and border basis detection

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 proposed by Gritzmann and Sturmfels (1993) [12] and it was shown to be NP-hard by Sturmfels and Wiegelmann. We investigate the computational complexity 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.