Satisfiability Algorithm With A Random Step

The satisfiability problem is to study to decide that whether there exists a truth assignment which can satisfy a given logical expression.SAT problem is very important to mathematical logic,artificial intelligence,computer algorithm design and analysis,engineering applications and other fields.SAT problem is the first problem which was proven NP-complete.It plays a very important role in computational complexity theory.Solving SAT problem generally divides into complete algorithm and non-complete algorithm.If an instance of SAT has a satisfiable problem,then complete algorithm can find the solution or else complete algorithm can prove that all solutions are not satisfiable.But this will cost exponential time.Non-complete algorithm can find a solution to an SAT instance with a large probability.Although it cannot find solutions for some SAT instance which has little solutions,it can be finished in polynomial time.So we applied non-complete algorithms to a lot of fields.Random algorithm is an important algorithm for solving SAT problem.It introduces randomization into algorithm and algorithm chooses the next operation according to random number.The normal frame of random algorithm is this:choose a solution for a given SAT instance,validate the solution for satisfiability,if the SAT instance is satisfied,then exit the algorithm;or else choose next solution according to random number until find a or t satisfiable solution.We use random source to create random number in random algorithm,but we hardly get hold of the random source.In practice the random source is replaced by pseudo-random machine,which is a fatal weakness for this algorithm.There are two ways to improve it:the first way is to improve the pseudo-random machine;the second way is to reduce the random numbers and dependence of random bit as best as we can and the performance of algorithm is not to be changed.This paper studies the latter approach.We introduce expander graph into random algorithm and use the properties of expander graph to induce random steps in algorithm,which reduce pseudorandomness,then we can reduce the dependence of random numbers and affection to the algorithm due to pseudorandomness.If the generic random algorithm search t solutions and every solution needs n pseudo-random codes(n is the number of variables in SAT instance),then it needs tn pseudo-random codes.But the algorithm in this paper only needs n+(t-1)log₂ n pseudo-random codes,which reduces pseudo-random codes and affection to the algorithm due to pseudorandomness.