Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal

Details:

   
TitleStructural Gröbner Basis Detection
Author(s) Bernd Sturmfels, Markus Wiegelmann
TypeTechnical Report, Misc
AbstractWe 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.
Length8
File
LanguageEnglish
NumberTR-96-017
AddressBerkeley, CA
Year1996
MonthMay
Edition0
Translation No
Refereed No
Webmaster