A Probabilistic Approach to Satisfiability of Propositional Logic Formulae

2019/12/04 by Russel, Reazul Hasan
#Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.1912.02150

Abstract

We propose a version of WalkSAT algorithm, named as BetaWalkSAT. This method uses probabilistic reasoning for biasing the starting state of the local search algorithm. Beta distribution is used to model the belief over boolean values of the literals. Our results suggest that, the proposed BetaWalkSAT algorithm can outperform other uninformed local search approaches for complex boolean satisfiability problems.

Related

• An Efficient Implementation for WalkSAT
• Solving Boolean Satisfiability Problems Using A Hypergraph-based Probabilistic Computer
• A New Approach to CNF-SAT From a Probabilistic Point of View
• Solving satisfiability by Bayesian inference
• An Algorithm for Computing Probabilistic Propositions