利用膨胀图求解SAT问题

摘要

一般的求解SAT问题的随机算法是对一个CNF公式的解进行f次随机搜索，共需要tn(n为变元个数)个随机位。本文提出的算法，利用膨胀图的性质诱导随机步搜索CNF公式的t个解，只需要(n+tlogn)位随机位，降低了算法对随机位的依赖。