Combining the k-CNF and XOR Phase-Transitions.

Jeffrey M. Dudek, Kuldeep S. Meel, Moshe Y. Vardi

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:

  1. 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.
  2. 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.

Heatmap of satisfiability for k=3, showing the sharp transition between k-CNF and XOR constraints.

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.

Theoretical phase-transition boundary for k-CNF-XOR formulas as established by Theorem 2.

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

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.
BibTeX
@inproceedings{dudek2016combining,
  author = {Jeffrey M. Dudek and Kuldeep S. Meel and Moshe Y. Vardi},
  title = {{Combining the k-CNF and XOR Phase-Transitions.}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure