Abstract
The runtime performance of modern SAT solvers on random k-CNF formulas is deeply connected with the 'phase-transition' phenomenon seen empirically in the satisfiability of random k-CNF formulas. Recent universal hashing-based approaches to sampling and counting crucially depend on the runtime performance of SAT solvers on formulas expressed as the conjunction of both k-CNF and XOR constraints (known as k-CNF-XOR formulas), but the behavior of random k-CNF-XOR formulas is unexplored in prior work. In this paper, we present the first study of the satisfiability of random k-CNF-XOR formulas. We show empirical evidence of a surprising phase-transition that follows a linear trade-off between k-CNF and XOR constraints. Furthermore, we prove that a phase-transition for k-CNF-XOR formulas exists for k = 2 and (when the number of k-CNF constraints is small) for k > 2.
Introduction
In Boolean Satisfiability (SAT), random formulas undergo a phase transition: as constraints are added to a fixed number of variables, the probability of satisfiability drops abruptly from nearly 100% to 0%. This "tipping point" is where SAT solvers struggle most, making it critical for algorithm design. While phase transitions for pure $k$-CNF and pure XOR (parity) logic are well-understood, modern hashing-based algorithms for counting and sampling solutions rely on formulas that combine both. This paper presents the first systematic study of $k$-CNF-XOR formulas, mapping how these constraint types interact and trade off against each other.
Methodology
The authors employed a dual approach to explore the $k$-CNF-XOR space:
- Empirical Exploration: Using CryptoMiniSAT, they generated thousands of synthetic formulas with variables ($n$) ranging from 25 to 150 and $k \in \{2, 3, 4, 5\}$. They varied the density of $k$-CNF clauses ($r$) and XOR clauses ($s$) to create high-resolution satisfiability heatmaps.
- Theoretical Proofs: Using probabilistic combinatorics and spin-glass theory (specifically free-entropy density), they established existence proofs for the phase transition at $k=2$ and for small $k$-CNF densities when $k > 2$. Explicit upper and lower bounds were derived using Markov’s and Chebyshev’s inequalities.
The k-CNF-XOR Phase Transition
The most striking empirical finding is a linear trade-off between $k$-CNF and XOR constraints. To maintain a formula at the "edge" of satisfiability, adding one type of constraint requires a proportional removal of the other.
Experimental data also revealed a "kink" or change in slope at high $k$-CNF densities, suggesting the solution space geometry changes when standard logic dominates. Theoretically, XOR constraints act as "filters" on the $k$-CNF solution space; by bounding the number of solutions in the $k$-CNF portion, the authors could predict the XOR density needed to eliminate all solutions.
Theoretical Results and Validation
The paper's theoretical framework connects the phase transition location to the free-entropy density of the $k$-CNF formula.
Key results include:
- Theorem 1: Formally establishes the existence of a phase transition for $k \ge 2$ at small $k$-CNF densities.
- Theorem 2: Provides concrete bounds, showing the transition is roughly bounded by $s > r \log_2(1 - 2^{-k}) + 1$.
- Consistency: The results recover known transition points for pure XOR ($s=1$) and pure $k$-CNF (e.g., $r \approx 4.26$ for 3-SAT) when the opposing constraint type is absent.
Conclusion and Future Work
While this work provides the first map of the $k$-CNF-XOR landscape, several challenges remain. The empirical results are limited to $n \le 150$ due to SAT complexity, and the nature of the observed "kink" requires further characterization. Future research should also investigate solver runtime across this mixed space—a critical factor for hashing-based algorithms—and seek to prove the transition for the entire range of $k$-CNF densities for $k > 2$.
Summary updated