The Phase Transition Analysis for Random Regular Exact (s, c, k)—SAT Problem
Xiaoling Mo, Daoyun Xu, Xi Wang · IEEE Access · 2021
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 {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.