Deterministic Algorithms for Solving Boolean Polynomial Equations Based on Channel Coding Theory

Abstract

Solving the satisfiability problems of Boolean polynomial equations is still an open challenge in the fields of mathematics and computer science. In this paper, our goal is to propose a non-algebraic method for solving maximal Boolean polynomial equations (Max-PoSSo problem). By leveraging channel coding theory and dynamic programming, we propose three deterministic and robust algorithms for solving the satisfiability problems of Boolean polynomial equations. Comparisons are made among the three proposed algorithms and Genetic and Gröbner algorithms. Simulation results show that the proposed algorithms exhibit better performance in terms of the largest number of Boolean polynomials equal to 0 compared to the benchmark schemes in the literature.

Keywords

• Boolean polynomial equations
• non-algebraic
• channel coding theory
• deterministic
• robust