A Random Algorithm for SAT Problem
Daoyun Xu · Journal of Guizhou University · 2007
In this paper,we proposed a random algorithm to solve the SAT problem.This algorithm transform firstly a CNF formula to a corresponding DNF formula and estimate the number Y of satisfiable solutions of the DNF formula.Comparing the Y with 2n,we can estimate the probability of satisfiable solution of CNF formula and judge whether the CNF formula is satisfiable or not.