RESEARCH PROGRESS OF BOOLEAN SATISFIABILITY PROBLEM

The Boolean satisfiability problem is a kind of NP-complete problem, which is widely used in artificial intelligence and machine learning. Based on the research of satisfiability problem in recent years, the definition of satisfiability problem and the feature of factor graph were introduced. From the structural characteristics of satisfiability problem, phase transformation, treewidth and decomposition, structural entropy and so on were introduced. The algorithms were divided into four categories (completeness algorithm, message passing algorithm, stochastic local search algorithm and intelligent optimization algorithm). The practical application of satisfiability problem was analyzed. The development trend of satisfiability research was prospected and summarized.