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<n<1000$
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?
Best Answer
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.
You can efficiently enumerate all solutions to the exact cover problem via Knuth's Algorithm X.