一类布尔方程组的可满足性阈值研究*

以一类布尔方程组形式的NP问题可满足性阈值估计为研究目的，通过将高斯消去算法与摘叶算法相结合的方法给出了一种求解该问题的完全算法，并通过不同参数条件下对大量随机实例进行数值实验得到了原问题可满足性阈值的算法估计值。所得研究结果不仅首次给出了该问题的可满足性阈值估计，而且可以作为相关启发式完全算法的设计依据。

Research on satisfiability threshold of class of Boolean equations

This paper focused on the satisfiability threshold of the NP problem which consisted of a class of Boolean equations.By the method of mixing Gauss-elimination algorithm and leaf-removal algorithm,proposed a new effective complete algorithm to achieve the solutions.Obtained the estimation of the satisfiability threshold of the original problem by numerical experiments on large scale of instances with different parameter values.The results not only approximate the satisfiability threshold firstly,but also provide the basis to design heuristics algorithms for NP problems with the form of Boolean equations.