版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构: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.