The Hard Problems Are Almost Everywhere For Random CNF-XOR Formulas

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

Abstract

This study provides a comprehensive analysis of the computational difficulty associated with CNF-XOR formulas, which are critical for modern hashing-based sampling and counting. By combining empirical solver performance data with theoretical probabilistic analysis, the authors reveal that these hybrid constraints lead to exponential scaling in solver runtime across a broad range of parameters. A key finding is the "shattering" of the solution space into distant, isolated clusters, a phenomenon proven to occur at nearly any XOR density. This structural property makes CNF-XOR formulas fundamentally challenging for modern SAT solvers.

Introduction

The Boolean Satisfiability Problem (SAT) is a cornerstone of computational complexity. While standard Conjunctive Normal Form (CNF) formulas are well-studied, a hybrid class known as CNF-XOR formulas has become essential for advanced AI tasks like solution counting and uniform sampling. These formulas combine standard logic with parity constraints (XOR). Despite their utility, the landscape of their computational hardness has remained largely unmapped. This research seeks to identify the "hard zones" where solvers struggle and provide a theoretical basis for this difficulty.

Methodology

The researchers employed a dual approach. Empirically, they tested CryptoMiniSAT, a state-of-the-art solver optimized for hybrid formulas, against thousands of synthetic 3-CNF-XOR instances. They varied three parameters: CNF density ($r$), XOR density ($s$), and XOR width ($p$). By measuring median runtimes as the number of variables ($n$) increased from 10 to 350, they could statistically determine the scaling behavior.

Exponential scaling of solve time as a function of the number of variables $n$.

Theoretically, the authors used probabilistic methods to examine the geometry of the solution space. They specifically looked for "shattering," where solutions form clusters separated by large Hamming distances, hindering the solver's ability to navigate the search space.

Results and Discussion

The empirical results confirm that exponential scaling is the norm for CNF-XOR formulas. The median runtime follows $2^{\alpha n}$, with the scaling factor $\alpha$ ranging between 0.05 and 0.4. Unlike pure CNF formulas, which are typically hard only near a specific phase transition, CNF-XOR formulas exhibit exponential hardness across a wide range of densities.

The scaling factor $\alpha$ as a function of XOR-clause density $s$ for various CNF densities $r$.

A significant insight is the "shattering effect." Theorem 2 in the paper provides a formal proof that for a wide range of variable probabilities, the solutions are $\Omega(n)$-separated. This structural barrier explains why solvers cannot easily move between solution clusters. Furthermore, the study debunked the intuition that shorter XOR clauses (lower $p$) necessarily simplify the problem; scaling behavior remains difficult even as width decreases.

Conclusion

This work maps the "hard zones" of the CNF-XOR landscape, showing that hardness is pervasive rather than localized. While the study identifies the causes of solver struggle—specifically the shattering of the solution space—it also highlights areas for future work, such as investigating "ultra-short" XOR clauses and developing new heuristics to navigate these fragmented solution spaces.

Summary updated

Abstract

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 CNF constraints and variable-width XOR constraints (known as CNF-XOR formulas). In this paper, we present the first study of the runtime behavior of SAT solvers equipped with XOR-reasoning techniques on random CNF-XOR formulas. We empirically demonstrate that a state-of-the-art SAT solver scales exponentially on random CNF-XOR formulas across a wide range of XOR-clause densities, peaking around the empirical phase-transition location. On the theoretical front, we prove that the solution space of a random CNF-XOR formula 'shatters' at all nonzero XOR-clause densities into well-separated components, similar to the behavior seen in random CNF formulas known to be difficult for many SAT algorithms.
BibTeX
@inproceedings{dudek2017hard,
  author = {Jeffrey M. Dudek and Kuldeep S. Meel and Moshe Y. Vardi},
  title = {{The Hard Problems Are Almost Everywhere For Random CNF-XOR Formulas}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/84},
}
Figure