The Phase Transition Analysis for Random Regular Exact (s, c, k)—SAT Problem
Open Access
- 8 February 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 9, 26664-26673
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
Funding Information
- National Natural Science Foundation of China (61762019, 61862051, 62062001)
This publication has 12 references indexed in Scilit:
- Charting the Replica Symmetric PhaseCommunications in Mathematical Physics, 2018
- Phase transitions in theq-coloring of random hypergraphsJournal of Physics A: Mathematical and Theoretical, 2017
- Warning Propagation Algorithm for the MAX-3-SAT ProblemIEEE Transactions on Emerging Topics in Computing, 2017
- Analyzing Walksat on Random FormulasSIAM Journal on Computing, 2014
- On the phase transitions of random k-constraint satisfaction problemsArtificial Intelligence, 2011
- On the satisfiability threshold of formulas with three literals per clauseTheoretical Computer Science, 2009
- Random k‐SAT: Two Moments Suffice to Cross a Sharp ThresholdSIAM Journal on Computing, 2006
- Threshold values of random K‐SAT from the cavity methodRandom Structures & Algorithms, 2005
- The probabilistic analysis of a greedy satisfiability algorithmRandom Structures & Algorithms, 2005
- Survey propagation: An algorithm for satisfiabilityRandom Structures & Algorithms, 2005