# Where is the theory about “binary toggling games”?

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.