Search Results

Because CDCL produces proofs in the Resolution proof system, problems provably hard for Resolution are also provably hard for CDCL. Exponentially shorter proofs can sometimes be found using stronger proof systems such as Res(⊕), a generalization of Resolution to XNF formulas, whose constraints are disjunctions of parity equations ("linear clauses") such as (x ⊕ y)∨¬(y ⊕ z). While some modern solvers like CryptoMiniSAT reason on Boolean clauses with separate parity equations, reasoning about more general linear clauses is less explored. We present CDCL(⊕), a generalization of CDCL to XNF formulas, and prove a bidirectional connection with Res(⊕): CDCL(⊕) not only produces Res(⊕) proofs, but also polynomially simulates Res(⊕) given nondeterministic decisions and restarts, mirroring the classical relationship between CDCL and Resolution. Our key technical tool is a new set of inference rules for Res(⊕) that helps us translate Resolution-based subroutines such as 1-UIP clause learning. Altogether, CDCL(⊕)’s parity reasoning includes branching on arbitrary parity equations, linear-algebraic reasoning during unit propagation, and learning linear clauses through conflict analysis. We provide a proof-of-concept implementation of CDCL(⊕) called Xorcle, which includes adaptations of existing CDCL heuristics to XNF formulas and an extension of LRUP proof logging that we call LRUP(⊕). On a selected suite of benchmarks focusing on native XNF formulas, Xorcle outperforms existing solvers such as Kissat and CryptoMiniSAT. Additionally, on Tseitin formulas written in CNF, even without preprocessing, Xorcle’s running time appears to scale nearly polynomially.