一个求解SAT问题的随机算法

A Random Algorithm for SAT Problem

本文中引入了一个求解满足性问题的随机算法。在该算法中,利用CNF公式转换为其对偶式——DNF公式,通过对满足DNF公式的真值赋值数Y作出估计。根据Y与2n比较结果,对CNF公式的可满足性进行估计并对其满足性进行判断。

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 2＂, we can estimate the probability of satisfiable solution of CNF formula and judge whether the CNF formula is satisfiable or not.