Solving special boolean equation set

Question

I have boolean equation sets that look like this (where ^ means xor):

eq 1: x1^x3^x5^x6^x9^x10^x11^x13^x17^x18 = 0

eq 2: 1^x1^x3^x10^x12^x17 = 0

eq 3: 1^x2^x3^x5^x8^x10^x14^x16 = 0

eq 4: 1^x4^x5^x6^x7^x8^x10^x16^x17 = 0

eq 5: x2^x5^x8^x11^x13^x14^x17^x18 = 0

(This example has 18 vars and 5 equations, but imagine a thousand variables with a hundred equations).

I can easily find solutions for this by successive subtitutions, but is there any way to quickly generate solution(s) with the least number of variables set to true ?

Thanks!

Answer 1

We can phrase the problem as follows:

Given $M \in \mathbb{F}_2^{m\times n}$ and $b \in \mathbb{F}_2^m$ with $n>m$, find the solution $x \in \mathbb{F}_2^n$ to $Mx=b$ for which $\sum_{i=1}^n x_i$ is minimized.

That is, this may be regarded as a "linear programming" problem, of sorts. Below is my initial attempt at a solution, which was not particularly fruitful.

---

We can write this particular system as the matrix equality $$ M\,x = b $$ Where $M$ is the matrix of coefficients (either $1$ or $0$) of $x_1,\dots,x_{18}$, $x = \pmatrix{x_1&\dots&x_{18}}^T$, and $b = \pmatrix{0&1&1&1&0}^T$ (corresponding to whether the equation contains a "1^"). With row reduction, we can determine how many of $x_1,\dots,x_{18}$ are "free variables", i.e. variables that may be arbitrarily set to true or false. The key here is to note that we define multiplication and addition over these elements/coefficients in $\{0,1\}$ as follows: $$ a+b = a\text{ XOR } b\\ a\cdot b = a \text{ AND } b $$ This is the definition of $\mathbb{F}_2$.

---

Let's take an example. Suppose we have the system

x1 ^ x2 ^ x3 == 0
x2 ^ x3 ^ x4 == 1
x3 ^ x4 ^ x5 == 1

We can write this as $$ \pmatrix{ 1&1&1&0&0\\ 0&1&1&1&0\\ 0&0&1&1&1} \pmatrix{x_1 \\ \vdots \\ x_5} = \pmatrix{0 \\ 1 \\ 1} $$ We can now row reduce the augmented matrix $(M\mid b)$ to get $$ \pmatrix{ 1&1&1&0&0&0\\ 0&1&1&1&0&1\\ 0&0&1&1&1&1} \implies\\ \left( \begin{array}{cccccc} 1 & 0 & 0 & -1 & 0 & -1 \\ 0 & 1 & 0 & 0 & -1 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ \end{array} \right)= \left( \begin{array}{cccccc} 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ \end{array} \right) $$ That is, the system may be rewritten as

x1     ^     x4       == 1
    x2 ^           x5 == 0
         x3 ^ x4 ^ x5 == 1

So that $x_4,x_5$ may be freely chosen, and the values of $x_1,x_2,x_3$ may be solved for as

x1 == 1 ^ x4
x2 == x5
x3 == 1^x4^x5

Hope that makes sense.

---

NOTE: this may not be as useful for the particular problem as I originally thought.