Details:

Title
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.
Length	8
File
Language	English
Number	TR-96-017
Address	Berkeley, CA
Year	1996
Month	May
Edition	0
Translation	No
Refereed	No