Structural Grobner basis detection

作     者：Sturmfels, B Wiegelmann, M 

作者机构：UNIV CALIF BERKELEYDEPT MATHBERKELEYCA 94720 UNIV TRIERFACHBEREICH MATHD-54286 TRIERGERMANY 

出 版 物：《APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING》 (Appl Algebra Eng Commun Comput)

年 卷 期：1997年第8卷第4期

页      面：257-263页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Grobner basis variation of term orders NP-completeness polynomial time algorithm system of polynomial equations 

摘      要：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 in NP-complete in general, but solvable in polynomial time in two different situations, when m is fixed and when n - m is fixed. Our new algorithm for the second case determines a candidate set of leading terms by solving a maximum matching problem. This reduces the problem to linear programming.