UPPER BOUND ON THE SATISFIABILITY THRESHOLD OF REGULAR RANDOM (k, s)-SAT PROBLEM

摘要

We consider a strictly regular random (k,s)-SAT problem and propose a GSRR model for generating its instances. By applying the first moment method and the asymptotic approximation of the γth coefficient for generating function f(z)~λ, where λ and λ are growing at a fixed rate, we obtain a new upper bound 2~k log 2 - (k+ 1) log 2/2 + ∈_k for this problem, which is below the best current known upper bound 2~k log 2 + ∈_k. Furthermore, it is also below the asymptotic bound of the uniform k-SAT problem, which is known as 2~k log 2-(log 2 +1)/2 + o_k(1) for large k. Thus, it illustrates that the strictly regular random (k,s)-SAT instances are computationally harder than the uniform one in general and it coincides with the experimental observations. Experiment results also indicate that the threshold for strictly regular random (k, s)-SAT problem is very close to our theoretical upper bound, and the regular random (k,s)-SAT instances generated by model GSRR are far more difficult to solve than the uniform one in each threshold point.