关于“二进制切换游戏”的理论在哪里？

Question

让我们 - 使用参数 $ m，n $ 和 $ l $ -

1. 创建一个有序的大小集 $ m $ $ n $ -bit long Vectors $ v $ 随机初始化它们： $ v_k [i]= b \ sim bin（n= 1，p= 0.5）\ \留下我 \ {0 \ .. \ n-1 \}，\ forall k \ in \ {0 \ .. \ m-1 \} $ 。

2. 创建一个n位长向量 $ a_0 $ 并将其初始化为1。

3. 创建 $ m $ -bit long矢量 $ s $ 并随机初始化它以与任何 $ v_k $ 的方式相同。

4. 对于 $ i $ 从 $ 0 $ 到 $ M $ ，如果 $ s [i]= 1 $ ，那么 $ a_i= a_ { I-1} \ oplus v_k $ ，否则 $ a_i= a_ {i-1} $ ，导致 $ a_m $ $ m $ 步骤

5. 使用 $ a_m $ 与所有向量 $ v_k $ 并使他返回 $ s $ 或矢量 $ s $ 其中 $ s [i]= 1 $ 。因此， $ a_m \ oplus v_ {i_0} \ oplus v_ {i_1} \ oplus v_ {i_2} \ oplus \ ... \ \ oplus v_ {i_ {last}}= a_0 $ 。

一个简单的例子，带有 $ n= 4 $ 和 $ 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 $ \ lightarrow s= [1,0,1]，$ 因为 $ a_m \ oplus v_0 \ oplus v_2= [1,1,1,1,1] $

这个问题发生在我遇到的许多游戏中，从来没有真正过得很厉害，直到现在。出于这个问题的目的，我称之为“二进制切换游戏”。

我想知道的是：

• “二进制切换游戏”真正称为
• 是什么理论是它们：算法，它们的复杂性（类），边缘案例等。

你能提供链接吗？我希望他们存在。

Answer 1

“二进制切换游戏”通常只是在 gf（2）。< / p>

您的特定问题相当于GF（2）的以下内容：

$$ \ sum_i v_is_i= 1 + a_m $$

如果我们写入 $ \ vec {s}= [s_1，s_2，\ dots] ^ t $ 和 $ v= [v_1，v_2，\ dots] ^ t $ 我们发现您的问题实际上是gf（2）的简单矩阵方程： $$ v \ vec {s}= 1 + a_m $$

您可以使用GF（2）的高斯消除解决此问题。在您的示例中：

$$ left（\ begin {array} {ccc | c @} 1＆0＆0＆1 \\ 1＆0＆1＆0 \\ 0＆1＆1＆1＆1 \\ 1＆1和1＆0 \结束{array} \右）\ longrightarrow 左（\ begin {array} {ccc | c @} \ color {红色} 1＆0＆0＆0 \\ 0＆0和1＆1 \\ 0＆1＆1＆1＆1 \\ 0＆1和1＆1 \结束{array} \右）\ longrightarrow 左（\ begin {array} {ccc | c @} 1＆0＆0＆1 \\ 0＆\ color {红色} 1＆1＆1 \\ 0＆0和1＆1 \\ 0＆0＆0＆0 \结束{array} \右）\ longrightarrow 左（\ begin {array} {ccc | c @} 1＆0＆0＆1 \\ 0＆1＆0＆0 \\ 0＆0＆\ color {红色} 1＆1 \\ 0＆0＆0＆0 \结束{array} \右） $$

从中可以读取该 $ s_1= 1 $ ， $ s_2= 0 $ 和 $ s_3= 1 $ 。