The Phase Transition Analysis for Random Regular Exact (s, c, k)—SAT Problem

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.

Keywords

• First moment method
• phase transition
• satisfiability problem
• second moment method