Complexity of Grobner basis detection and border basis detection
Grobner 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 Grobner 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. (C) 2012 Elsevier B.V. All rights reserved.
complexity grobner basis detection zero-dimensional ideals border bases