|Title||Structural Gröbner Basis Detection|
|Author(s)|| Bernd Sturmfels, Markus Wiegelmann|
|Type||Technical Report, Misc|
|Abstract||We determine the computational complexity of deciding whether m|
polynomials in n variables have relatively prime leading terms with
respect to some term order. This problem is NP-complete in general, but solvable in polynomial time for m fixed and for n - m fixed. Our new algorithm for the latter case determines a candidate set of leading terms by solving a maximum matching problem. This reduces the problem to linear programming.