Abstract
The length of each clause in a regular (s, c, k) - CNF formula is k. Each argument occurrences s times, among them, positive occurrences (c * s) times and negative occurrences (s - c * s) times, where 0 < c < 1. A regular exact (s, c, k) - SAT question refers to whether there is a set of Boolean variable assignment such that exactly one literal in each clause of the regular (s, c, k) - CNF formula is true. Obviously, the problem is a NP-hard problem. To understand the hardness and the distribution of satisfiable solutions of regular exact (s, c, k) - SAT problem, we introduce a random instance generation model, use the first moment and second moment methods to analyze the satisfiable phase transition of the solutions. Set s* is the phase transition point, we show that the stochastic regular exact (s, c, k) - SAT problem instance is satisfiable with high probability if s < s* and unsatisfiable with high probability if s > s*, among them, s* is a function about a parameter c. Further, we discuss the phase transition point of the random regular exact (s, r, k) - SAT problem – the difference between the positive and negative occurrences of the variable is r - is s*. Finally, through several groups of experimental data to verify, the experimental results are consistent with the theory, and prove the correctness of the theory.
Funding Information
  • National Natural Science Foundation of China (61762019, 61862051, 62062001)

This publication has 12 references indexed in Scilit: