On the Efficiency of Solving Boolean Polynomial Systems with the Characteristic Set Method
On the Efficiency of Solving Boolean Polynomial Systems with the Characteristic Set Method
复制标题
DOI：
10.1016/j.jsc.2019.11.001
复制
发表时间：
2014-05
期刊：
影响因子：
--
通讯作者：
Zhenyu Huang;Yao Sun;D. Lin
中科院分区：
文献类型：
--
作者：
Zhenyu Huang;Yao Sun;D. Lin
提出了一种求解布尔多项式系统的改进特征集算法。该算法的基本思想是通过零分解将所有多项式转化为一元多项式，并利用加法得到伪多项式。算法中应用了三个重要技术。第一种是用新生成的线性多项式消去变量。二是优化零分解多项式的选取策略。第三种方法是计算加法器以消除新生成的monic多项式的首变量。通过对零分解树深度的分析，给出了该算法的复杂度界，这些复杂度界低于以往特征集算法的复杂度界。大量的实验结果表明，该算法比以往的特征集算法更有效地解决布尔多项式系统。
An improved characteristic set algorithm for solving Boolean polynomial systems is proposed. This algorithm is based on the idea of converting all the polynomials into monic ones by zero decomposition, and using additions to obtain pseudo-remainders. Three important techniques are applied in the algorithm. The first one is eliminating variables by new generated linear polynomials. The second one is optimizing the strategy of choosing polynomial for zero decomposition. The third one is to compute add-remainders to eliminate the leading variable of new generated monic polynomials. By analyzing the depth of the zero decomposition tree, we present some complexity bounds of this algorithm, which are lower than the complexity bounds of previous characteristic set algorithms. Extensive experimental results show that this new algorithm is more efficient than previous characteristic set algorithms for solving Boolean polynomial systems.