language: en

INTERNATIONAL COMPUTER SCIENCE INSTITUTE
I 1947 Center St. * Suite 600 * Berkeley, California 94704-1198

[* (510) 643-9153 * FAX (510) 643-7684]

Structural Grobner Basis Detection

Bernd Sturmfels and Markus Wiegelmann
TR-96-017
Department of Mathematics, UC Berkeley
Berkeley, California 94720, USA
bernd@math.berkeley.edu
Fachbereich Mathematik, Universitat Trier
Universitatsring 15, D-54286 Trier, Germany
wiegelm@uni-trier.de

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 nm 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.