IndisputableMonolith.Complexity.SAT.XOR
This module defines XORConstraint and XORSystem for parity constraints over Fin n variables in SAT problems. Complexity researchers working on mixed CNF/XOR instances cite it as the base layer for backpropagation and geometric families. It consists entirely of definitions and basic operations with no theorems or proofs.
claimAn XOR constraint over $n$ variables is a pair $(S,p)$ with $Ssubseteqmathrm{Fin}n$ and $p in{0,1}$ requiring $bigoplus_{i in S}x_i=p$. An XOR system is a finite list of such constraints.
background
The upstream CNF module fixes variable indices as elements of Fin n. This module introduces XORConstraint to capture a subset parity requirement and XORSystem to collect multiple such constraints, together with the auxiliary operations parityOf, satisfiesXOR and satisfiesSystem. The setting is standard propositional SAT extended by linear equations over GF(2).
proof idea
This is a definition module, no proofs.
why it matters in Recognition Science
The module supplies the primitive XOR objects required by Backprop (partial assignments), Completeness (total-assignment lifting), GeoFamily (Morton-octant masks), Isolation, PC (mixed CNF/XOR clauses) and SmallBias (explicit small-bias families). It therefore sits at the root of all downstream SAT-XOR constructions in the complexity layer.
scope and limits
- Does not contain decision procedures or solvers for XOR-SAT.
- Does not prove NP-completeness or complexity bounds.
- Does not encode geometric Morton masks (those appear only in GeoFamily).
- Does not reference Recognition Science forcing chain or physical constants.
- Does not handle weighted or probabilistic variants of parity constraints.