Where is the theory about “binary toggling games”?

Question

Let us -- using parameters $M, N$ and $L$ --

1. create an ordered set of size $M$ of $N$-bit long vectors $V$ and initialize them randomly: $V_k[i] = b \sim Bin(n=1, p=0.5)\ \forall i \in \{0\ ..\ N-1\}, \forall k \in \{0\ ..\ M-1\}$.

2. create an N-bit long vector $A_0$ and initialize it to ones.

3. create an $M$-bit long vector $S$ and initialize it randomly in the same manner as any $V_k$.

4. for $i$ from $0$ to $M$, if $S[i] = 1$, then $A_i = A_{i-1} \oplus V_k$, otherwise $A_i = A_{i-1}$, resulting in $A_M$ after $M$ steps

5. present an agent/player with $A_M$ together with all vectors $V_k$ and make him return $S$ or the set of indices of vector $S$ where $S[i] = 1$. It follows that $A_M \oplus V_{i_0} \oplus V_{i_1} \oplus V_{i_2} \oplus\ ...\ \oplus V_{i_{last}} = A_0$.

A simple example with $N=4$ and $M=3$:

$A_M = [0, 1, 0, 1]$, $V_0 = [1, 1, 0, 1]$, $V_1 = [0, 0, 1, 1]$, $V_2 = [0, 1, 1, 1]$

solution $\rightarrow S = [1, 0, 1],$ because $A_M \oplus V_0 \oplus V_2 = [1, 1, 1, 1]$

This problem occurs in many games I have encountered and never really gave it much thought, until now. For the purpose of this question, I have called it the "binary toggling game".

What I wonder is:

• what are "binary toggling games" really called
• what is the theory being them: algorithms, their complexity (classes), edge cases, etc.

Could you please provide links? I hope they exist.

Answer 1

"Binary toggling games" are generally just arithmetic problems over GF(2).

Your particular problem is equivalent to the following over GF(2):

$$\sum_i V_iS_i = 1 + A_M $$

If we write $\vec{S} = [S_1, S_2, \dots]^T$ and $V = [V_1, V_2, \dots]^T$ we find that your problem is actually a simple matrix equation over GF(2): $$V\vec{S} = 1 + A_M$$

You can solve this problem using Gaussian elimination over GF(2). In your example:

$$\left(\begin{array}{ccc|c@} 1 & 0 & 0 & 1\\ 1 & 0 & 1 & 0\\ 0 & 1 & 1 & 1\\ 1 & 1 & 1 & 0 \end{array}\right) \longrightarrow \left(\begin{array}{ccc|c@} \color{red}1 & 0 & 0 & 1\\ 0 & 0 & 1 & 1\\ 0 & 1 & 1 & 1\\ 0 & 1 & 1 & 1 \end{array}\right)\longrightarrow \left(\begin{array}{ccc|c@} 1 & 0 & 0 & 1\\ 0 &\color{red}1 & 1 & 1\\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 \end{array}\right)\longrightarrow \left(\begin{array}{ccc|c@} 1 & 0 & 0 & 1\\ 0 &1 & 0 & 0\\ 0 & 0 & \color{red}1 & 1\\ 0 & 0 & 0 & 0 \end{array}\right) $$

From which we can read off that $S_1 = 1$, $S_2 = 0$ and $S_3 = 1$.