Introduction
Generating "hard" satisfiable instances for Boolean Satisfiability (SAT) solvers is a persistent challenge in computer science. While unsatisfiable benchmarks are plentiful, random satisfiable formulas often lack the structural complexity of real-world problems, making them too easy for modern solvers. This paper, presented at AAAI 2006, investigates the regular XORSAT model as a solution, demonstrating that increasing the connectivity (degree) of constraint graphs creates problems that are exponentially more difficult to solve.
Methodology: The Regular $d$-XORSAT Generator
The core of this research is a generalized generator for regular $d$-XORSAT instances. In this model, every variable and every constraint has a fixed degree $d$. The generation process follows these steps:
- Graph Construction: A $d$-regular bipartite graph is created, linking $n$ variables to $n$ equations.
- Linear System Generation: A random "hidden" solution $z$ is chosen to ensure satisfiability, and the right-hand side $b$ is calculated such that $Az = b \pmod 2$.
- CNF Conversion: Each XOR equation is converted into $2^{d-1}$ Conjunctive Normal Form (CNF) clauses that forbid parity violations.
To handle higher degrees ($d > 3$), the author employs a matching-based approach, iteratively adding maximum matchings to build the $d$-regular structure.
Key Results and Solver Performance
The study evaluates these instances against standard DPLL-based solvers (like zChaff and Satz) and local search solvers (like WalkSAT).
Scaling with Degree $d$
The most striking finding is the relationship between the degree $d$ and problem hardness. As $d$ increases from 3 to 9, the computational effort required by solvers grows exponentially. For instance, even with a small set of 50 variables, a $d=9$ instance can demand over $10^6$ decisions from a state-of-the-art solver, representing a remarkably high hardness-to-size ratio.
Regularity vs. Randomness
The research highlights that regularity itself is a primary source of hardness. Regular $d$-XORSAT instances are significantly more difficult than their non-regular "random" counterparts. In regular graphs, expansion properties are uniform, preventing solvers from exploiting "weak points" or lowly-connected variables that are common in standard random models.
In head-to-head tests, regular $d$-XORSAT instances consistently required orders of magnitude more "branches" to solve than standard random $k$-XORSAT instances of the same size.
Conclusion
The regular $d$-XORSAT model provides a robust framework for generating hard satisfiable benchmarks. By simply increasing the degree $d$, researchers can create small but incredibly complex instances that challenge both DPLL and local search algorithms. Future work aims to provide a deeper theoretical understanding of why conflict-driven clause learning (CDCL) struggles with these specific structures and to find families where complexity converges to a truly exponential $\Omega(2^n)$.
Summary updated