随机多比特翻转算法求解布尔多项式方程组可满足性问题

摘要

布尔多项式方程组求解问题是数学与计算机科学中的难解之一,极大布尔多项式方程组可满足性问题是一般布尔多项式方程组求解问题的扩展问题.为了解决极大布尔多项式方程组可满足性问题,首先,提出了一种可证明是否存在满足全部函数为0的解的贪婪算法,结果是不存在满足256个函数全部为0的解;其次,提出了一种基于低密度奇偶校验码,比特翻转译码算法与随机数相结合的随机多比特翻转算法.%The problem of solving Boolean polynomial equations is one of the most difficult problems in mathematics and computer science, and the satisfiability problems of maximal Boolean polynomial equations is the extension of the solution of general Boolean polynomial equations. In order to solve the satisfiability problem of maximal Boolean polynomial equations, a greedy algorithm which can prove the existence of all functions as 0 solutions is proposed at first, and the results show that the solutions satisfying 256 functions are all 0 is non-existent;a random multi bit flipping algorithm is proposed combined with the bit flipping decoding algorithm of low-density parity check codes with random numbers.