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