Topological Tautologies for Redundancy-Based SAT Solvers

Topological existence theorems such as Tucker's lemma say that any labeling of a symmetric triangulated shape must contain a certain local pattern. Turned around, they give a family of unsatisfiable Boolean formulas. Each formula asks for a symmetric labeling that avoids every such pattern, and the theorem says none exists. We propose to build these formulas from the $\mathbb{Z}_p$-STAR-TUCKER lemma, a combinatorial lemma about labelings of complexes on which a cyclic group of prime order $p$ acts freely. We then ask whether the symmetry that makes the theorem true can also make it cheap to refute.

The hook is how a modern "satisfaction-driven" solver prunes its search. Such a solver may cut away a whole region of assignments, as long as it can show a transformation (a witness) that moves every solution in that region to a solution outside it. The $\mathbb{Z}_p$ group action is an obvious source of such transformations. We will generate candidate witnesses directly from the group action, test them in polynomial time, and measure whether this closes the gap between these formulas and the resolution-bound solvers that fail on them.

Core Claim

Two things are missing from the literature, and we supply both. The first is a benchmark family. Solvers that break past resolution are evaluated on pigeonhole, Tseitin parity, and Mutilated Chessboard formulas (Encoding Redundancy for Satisfaction-Driven Clause Learning; Learning Shorter Redundant Clauses in SDCL Using MaxSAT). Meanwhile, complexity theory has shown that Tucker-type principles are the natural complete problems for PPA and PPA-$p$. PPA and PPA-$p$ are the classes of search problems whose solutions are guaranteed by parity or mod-$p$ counting arguments (The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich; A Topological Characterization of Modulo-p Arguments and Implications for Necklace Splitting). Nobody has encoded these principles as CNF and run SAT solvers on them. For $p=2$ they are Tseitin-like parity principles, and for $p \ge 3$ they are mod-$p$ counting principles. Both kinds of reasoning are outside what clause learning can do cheaply.

The second is a witness source. We claim that witnesses built from the free $\mathbb{Z}_p$ action, applied locally to one vertex orbit and its neighborhood, can be checked in polynomial time. We further claim they yield short propagation-redundant clauses on these formulas. Such clauses would replace the NP-hard MaxSAT minimization step that MapleSDCL uses to shorten its learned clauses. Local application matters: a locally applied action is not a symmetry of the whole formula, so global symmetry-breaking cannot express it.

Solution-space topology enters as a diagnostic, not as the engine. A Topological Version of Schaefer's Dichotomy Theorem builds a shape from a formula's solution set, its "induced cubical complex": every subcube of $\{0,1\}^d$ whose corners are all solutions gets filled in. The paper shows that the holes of this shape, measured by its homology, track computational hardness. We borrow this shape to ask what our pruning does to the solution set. By construction, a group-action witness maps each removed solution onto its orbit partner. Pruning should therefore shrink the solution complex toward a fundamental domain of the action and leave its orbit-quotient topology intact. Nothing guarantees the same for clauses minimized by MaxSAT. This gives us a concrete handle on the open question of which redundant clauses a solver can safely delete (Improving and Understanding the Power of Satisfaction-Driven Clause Learning).

Research Program

Encodings. We will first write CNF encodings. The variables $x_{v,\ell}$ say that vertex $v$ of a triangulated complex with a free $\mathbb{Z}_p$ action carries label $\ell$. Equivariance clauses force the label of the rotated vertex $g v$ to equal the rotated label $g \cdot \ell$. Forbidding clauses exclude every local configuration whose existence the $\mathbb{Z}_p$-STAR-TUCKER lemma guarantees. The lemma makes the formula unsatisfiable. For $p=2$ we also encode 2D-Tucker, the starting point of the PPA reductions in The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich. We will also produce satisfiable search variants, which ask the solver to find the forced configuration, from the $k$-Polygon Tucker problems of A Topological Characterization of Modulo-p Arguments and Implications for Necklace Splitting. Instance families will vary the triangulation's size and dimension and take $p \in \{2,3,5\}$.

Witness generator. Second, we add a witness generator to MapleSDCL. When the solver reaches a partial assignment $\alpha$, the generator proposes witnesses $\omega = g^j \cdot \alpha|_{N(v)}$: it applies the $j$-th group element to the labels on a neighborhood $N(v)$ of one vertex orbit. The generator then runs the standard unit-propagation test for propagation redundancy. If some $\omega$ passes, the solver learns the short clause built from $\alpha|_{N(v)}$ and skips the MaxSAT call. There are $O(p \cdot |V|)$ candidates, each checked by unit propagation, so the whole step runs in polynomial time. Every proof will be checked by dpr-trim.

Topological diagnostic. Third, on instances small enough to enumerate (about 20 or fewer variables after dropping one forbidding constraint so that solutions exist), we compute the homology of the induced cubical complex, over $\mathbb{F}_p$, before and after each learned clause. We will record whether group-witness clauses and MaxSAT-minimized clauses differ in how they change the topology of the solution set.

Baselines

The naive reference point is plain clause learning: Kissat and MapleSAT run with default settings. On mchess19 these solvers timed out at 7,200 s, as reported in Improving and Understanding the Power of Satisfaction-Driven Clause Learning. We expect the same exponential growth on our Tucker families.

A second reference is plain clause learning plus the in-processing minimization of An Effective Learnt Clause Minimization Approach for CDCL SAT Solvers. That method shortens learned clauses at restarts using unit propagation. It is the best resolution-bound competitor, and it tests whether shorter clauses alone are enough.

The first satisfaction-driven baseline is SaDiCaL (Encoding Redundancy for Satisfaction-Driven Clause Learning). Its filtered positive reduct found pruning clauses quickly on parity formulas, solving Urquhart-s5 in under 3 s where competitors exceeded 3,600 s. Because Tseitin parity is the closest existing relative of the $p=2$ family, SaDiCaL is the natural threat there.

The strongest baseline is MapleSDCL with MaxSAT minimization (Learning Shorter Redundant Clauses in SDCL Using MaxSAT). It is the strongest because it already searches, by general optimization, for the shortest pruning clause that our generator targets structurally. Its reported results are an average of 100 s on mchess19, success up to mchess23, learned clauses about one-third the length of "only-decisions" clauses, and MaxSAT taking at most 30% of runtime. On any Tucker or $\mathbb{Z}_p$-STAR-TUCKER encoding, no reported result was found on Lacuna, so our runs will set its baseline.

For fairness, every solver gets the same CNF files, the same 7,200 s limit (matching the MCB protocol), the same hardware, and the same seeds. We run five seeds per instance, and parameters are tuned on the smallest instances of each family only.

Two ablations isolate the key ingredient. The first applies the group action to the whole assignment, not locally. That is equivalent to breaking a global symmetry and bounds what symmetry alone buys. The second draws random label permutations of the same neighborhood size in place of group elements. That tests whether the cyclic structure matters or only the fact that transformations are local.

We will count ourselves as beating MapleSDCL if two things hold on the $p \ge 3$ families. First, the largest instance solved within the limit must grow with a clearly better scaling exponent. Second, on the standard MCB, Tseitin, and PHP families, we must be no worse than MapleSDCL, where those families have a group structure our generator can use.

Why not just…?

Why not just run MapleSDCL or SaDiCaL unmodified on the new formulas? This is the real threat, and it is also our first experiment. If out-of-the-box MapleSDCL already refutes the $\mathbb{Z}_p$-STAR-TUCKER families at polynomial scaling, the witness generator is unnecessary. The paper then becomes a benchmark paper showing that satisfaction-driven solvers already capture mod-$p$ topological arguments, which is itself new. We expect them to struggle for $p \ge 3$. The existing reducts were designed and demonstrated on mod-2 and matching obstructions, and MaxSAT minimization is NP-hard at every call. Whether that expectation holds is settled by the scaling curves, not by argument.

Why not just break the symmetry statically with lex-leader-style constraints before solving? A global $\mathbb{Z}_p$ symmetry removes only a factor of $p$ from the search space. That cannot dent an exponential lower bound. The whole-assignment ablation implements exactly this and should expose that limit. Our witnesses act on one orbit's neighborhood, which does not preserve the formula, so static preprocessing cannot express them.

Why not just use shorter-clause heuristics inside ordinary clause learning? Unit-propagation minimization (An Effective Learnt Clause Minimization Approach for CDCL SAT Solvers) and common subclause elimination (Accelerating SAT Solving by Common Subclause Elimination) help on competition sets, for example a 21.15% speedup on SAT13 for subclause elimination. Both only shorten or factor clauses that resolution can already derive. They cannot introduce the clauses that remove solutions and that counting principles require. We run the minimization method as a baseline to confirm this on the new families.

Proposed Experiments

The decisive experiment is a scaling plot of solved instance size against time, per family and per $p$, for all solvers above. The proposal succeeds only if group-witness SDCL shows polynomial growth where MapleSDCL grows exponentially at $p = 3$ and $p = 5$. The random-permutation ablation must also fail where the group version succeeds.

Secondary measures come from the same runs: the length distribution of learned clauses (compared against MapleSDCL's one-third ratio), the fraction of runtime spent generating witnesses (compared against MaxSAT's 30%), and verification time in dpr-trim.

The topological diagnostic runs on small enumerable instances. It tests one prediction: group-witness clauses preserve the $\mathbb{F}_p$-homology of the orbit quotient of the solution complex, while some MaxSAT-minimized clauses change it. If that prediction holds, we will try a deletion policy that deletes only homology-preserving clauses, and measure whether it keeps short refutations while reducing time spent in unit propagation.