Article :Browse 2277 Download 2301
Received:July 05, 2016
Received:July 05, 2016
Abstract:This article studies the strictly regular (k,r)-SAT problem by restricting the k-SAT problem instances, where each variables occurs precisely r=2s times and each of the positive and negative literals occurs precisely s times. By constructing a special independent random experiment, the study derives an upper bound on the satisfiability threshold of the strictly regular random (k,r)-SAT problem via the first moment method. Based on the fact that the satisfiability threshold of the strictly regular and the regular random (k,r)-SAT problems are approximately equal, a new upper bound on the threshold of the regular random (k,r)-SAT problem is obtained. This new upper bound is not only below the current best known upper bounds on the satisfiability threshold of the regular random (k,r)-SAT problem, but also below the satisfiability threshold of the uniform random k-SAT problem. Thus, it is theoretically explained that in general the regular random (k,r)-SAT instances are harder to satisfy at their phase transition points than the uniform random k-SAT problem at the corresponding phase transition points with same scales. Finally, numerical results verify the validity of our new upper bound.
keywords: regular random (k,r)-SAT problem satisfiability threshold phase transition phenomena computational complexity
Foundation items:National Natural Science Foundation of China (61262006, 61463044, 61462001); Science and Technology Foundation of Guizhou Province of China (LKQS201313)
Reference text:
ZHOU Jin-Cheng,XU Dao-Yun,LU You-Jun.Satisfiability Threshold of the Regular Random (k,r)-SAT Problem.Journal of Software,2016,27(12):2985-2993
ZHOU Jin-Cheng,XU Dao-Yun,LU You-Jun.Satisfiability Threshold of the Regular Random (k,r)-SAT Problem.Journal of Software,2016,27(12):2985-2993