Exact Phase Transitions of Counting Solutions of Constraint Satisfaction Problems
Jing Shuang Shen, Xia Wang · 2024
Phase transition of constraint satisfaction problem plays an important role in computational complexity. In this paper, we use the first moment and the second moment to get phase transition of counting solutions of constraint satisfaction problems. We apply the method to counting the solutions of random k-SAT with moderately growing k and the model d-k-CSP. The threshold points of the two models are precisely located.