# Efficient solving of Boolean linear equations systems

Let us assume that we have a collection of 1000 boolean variables: $$x_1,...,x_{1000}$$

From this collection we sample 10 variables $$n$$ times with repetition; $$100

We construct a boolean expression $$B$$ by joining a XOR of all variables from a given sample by AND operators. So we have: $$(S_1) AND ... AND (S_{n})$$, where each $$(S_i)$$ may be represented as a XOR of 10 boolean variables. That exclusive alternative being defined in my case as: each $$(S_i)$$ is true if and only if exactly one boolean variable is true.

I would like to write a program which enumerates all possible combinations of values for the boolean variables that would satisfy $$B$$.

I am aware that the general SAT problem is NP-complete. However, special cases may be easier: XOR-SAT is in P class since it may be written as a system of linear equations modulo 2. But in that case the XOR is defined differently compared to my case: for XOR-SAT the XOR is effectively parity test (hence mod2).

I think we may construct a system of linear equations here too. Each equation would be a sum of all boolean variables and we require that each such sum equals to 1. I would implement this as a linear algebraic problem with matrices: $$Ax=b$$. $$A$$ would be also a boolean matrix with $$n$$ rows and 1000 columns; $$x$$ would have 1000 rows and 1 column (this represents the boolean variables); $$b$$ would have 1000 rows and 1 column totally filled with ones.

Is there any method to efficiently solve this system? I know that many standard methods do not work since they expect a system with exactly one solution. But here our domain is constrained since we operate on boolean variables. So maybe there would be a way to find out what combinations would satisfy $$B$$ by some clever matrix operations?

Or maybe I am completely wrong and I should approach the problem from a different angle?

Your $$Ax=b$$ is called a set partitioning or exact cover problem. Each row $$i$$ of $$A$$ corresponds to an element, and each column $$j$$ of $$A$$ corresponds to a set, with $$A_{ij}$$ indicating whether element $$i$$ appears in set $$j$$. The binary variable $$x_j$$ indicates whether set $$j$$ is chosen. The linear system expresses that each element appears in exactly one chosen set.
• Your $Ax=b$ is called a set partitioning problem. Each row $i$ of $A$ corresponds to an element, and each column $j$ of $A$ corresponds to a set, with $A_{ij}$ indicating whether element $i$ appears in set $j$. The binary variable $x_j$ indicates whether set $j$ is chosen. The linear system expresses that each element appears in exactly one chosen set. Apr 4, 2022 at 19:46