Degrees of Freedom for Critical Random 2-SAT

2025/05/21 by Andreas Basse-O'Connor, Basse-O'Connor, Andreas, Mette Skjøtt +1
Computer Science · #Advanced Graph Theory Research #Constraint Satisfaction and Optimization #FOS: Mathematics #Formal Methods in Verification #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2505.15940

openalex publication_date 2025/05/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The random k-SAT problem serves as a model that represents the 'typical' k-SAT instances. This model is thought to undergo a phase transition as the clause density changes, and it is believed that the random k-SAT problem is primarily difficult to solve near this critical phase. In this paper, we introduce a weak formulation of degrees of freedom for random k-SAT problems and demonstrate that the critical random 2-SAT problem has √[3]n degrees of freedom. This quantity represents the maximum number of variables that can be assigned truth values without affecting the formula's satisfiability. Notably, the value of √[3]n differs significantly from the degrees of freedom in random 2-SAT problems sampled below the satisfiability threshold, where the corresponding value equals √(n). Thus, our result underscores the significant shift in structural properties and variable dependency as satisfiability problems approach criticality.

Citations

• On the Regularity of Random 2-SAT and 3-SAT
• The number of random 2-SAT solutions is asymptotically log-normal
• Proof of the satisfiability conjecture for large k
• The SAT Phase Transition

Related

• On the Regularity of Random 2-SAT and 3-SAT
• Phase Transition in Unrestricted Random SAT
• Satisfiability Threshold for Power Law Random 2-SAT in Configuration\n Model
• Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold
• The SAT Phase Transition