检验结合律的随机算法

Posted on Edited on In

对于一个作用在有限集合$X$上的二元运算$\circ$，检验它是否满足结合律。

即：对于$\forall r,s,t\in X$，是否总有$(r\circ s)\circ t = r\circ(s\cdot t)$？

问题定义

Input: 一个二元运算$\circ$，一个有限集合$X$。

Output: “Yes”当且仅当$\forall r,s,t\in X,(r\circ s)\circ t = r\circ(s\cdot t)$；否则“No”。

平凡的解法

随机选取$r,s,t$，检查是否有$(r\circ s)\circ t = r\circ(s\cdot t)$。假设集合$X$的Cardinality为$n$，由于$r,s,t$都各有$n$种选法，所以算法复杂度为$O(n^3)$。

类似的，一个随机算法即为随机选择三元组$(r,s,t)\in X$。最坏情况下只有一组$(r^{w},s^{w},t^{w})$使得结合律不成立，那么仅有$1/n^3$的概率选到witness。

非平凡的解法

首先断言：存在一个复杂度仅为$O(n^2)$的单边错误随机算法。

算法的大致思路：重新设计一个集合，在新的集合中尝试寻找witness，并将error bound由之前降到与$n$无关的常数。

新集合的设计

新的集合$Y$为$X$的子集的集合（幂集），即$Y=2^X$。或将$i,j,k$视作一个线性空间的一组基，新的集合中元素定义为：

其中$\alpha_i\in\{0,1\}$，0表示不选，1表示选。新的集合中共有$2^n$个元素。

对新的集合定义各类运算：

  • 定义+：$R+S = \sum_{i\in X}r_i \cdot i+\sum_{i\in X}s_i\cdot i = \sum_{i\in X}(r_i+s_i)\cdot i$

  • 定义$\circ$：$R\circ S=(\sum_{i\in X} r_i\cdot i)\circ(\sum_{j\in X} s_j\cdot j)=\sum_{i,j \in X}(r_i\cdot s_j)\cdot(i\circ j)$

  • 定义数乘：$\alpha R = \alpha \sum_{i\in X}r_i\cdot i = \sum_{i\in X}(\alpha r_i)\cdot i$

（注：所有参数的运算都在模2意义下进行；二元运算 $\circ$的定义是平凡的，其实就是直接对$X$上的运算进行展开）

运算的等价性

现在考虑$\circ$运算在两个集合中的等价性。

显然，如果$\circ$在旧的集合$X$中存在结合律，则在新的集合$Y$中也一定存在结合律，这是由于$Y$中的运算为在$X$中的直接展开；

若新的集合$Y$中存在结合律，那么旧的集合$X$中也一定存在，这是由于$X$总为$Y$的一个特例。

因此，$\circ$在$X$中存在结合律与在$Y$中存在结合律是等价的。

算法设计

从集合$Y$中随机选择三元组$R,S,T$，检查是否有$(R\circ S)\circ T - R\circ(S\circ T)=0$。若否，输出“No”；若是，输出“Yes”。

该算法的复杂度为$O(n^2)$，这是由于计算$R\circ S$需要$O(n^2)$的运行时间，因此计算上式左边需要$4O(n^2)$的运行时间，总共仍为$O(n^2)$。下面证明该算法是常数单边错误的。

错误率分析

下面证明：如果$\circ$不满足结合律，那么三元组$R,S,T$为witness的概率为$1/8$，或：

证明：

如果$\circ$不满足结合律，那么一定有一组$(r^{w},s^{w},t^{w})$作为witness，使得$(r^{w}\circ s^{w})\circ t^{w}\neq r^{w}\circ(s^{w}\circ t^{w})$。

在此基础上，我们可以将三元组$(R,S,T)\in Y^3$分为8类。其中，$R_0, S_0, T_0$表示所有满足$r^{w}\notin R_0,s^{w}\notin S_0,t^{w}\notin T_0$的元素。定义$R_1 = R_0\cup \{r^{w}\},S_1 = S_0\cup\{s^{w}\},T_1=T_0\cup\{t^{w}\}$。

（即向$R_0$中添加$r^{w}$，$S_0$中添加$s^{w}$，$T_0$中添加$t^{w}$构造出$R_1,S_1,T_1$）

因此$Y^3$可以分为8个一组，表示为：$(R_i,S_j,T_k),i,j,k\in\{0,1\}$。

分别在$X$和$Y$上定义函数$f$，用以计算结合律是否成立。

利用容斥原理，可以将$f(r^{w},s^{w},t^{w})$用上述8个三元组$(R_i,S_j,T_k),i,j,k\in\{0,1\}$表示：

由于$(r^{w}\circ s^{w})\circ t^{w}\neq r^{w}\circ(s^{w}\circ t^{w})$，那么$f(r^{w},s^{w},t^{w})\neq 0$，因此上式右边的8个式子中必然有至少一个非0（若全为0则与等式左边非0矛盾），因此按照上述的划分方式，$Y^3$中的任何一组8个三元组中必有一个非0。

因此选到witness的概率至少为$1/8$，即出错率至多为$7/8$。

回顾——前面提到的算法中，三元组$r,s,t$为witness的概率为$1/n^3$（或出错概率为$1-1/n^3$）。而该算法直接将出错率降到了常数。