代数与计算 整理与思考

Lecture 1

课程介绍：

(1) 图同构的群论算法。

(2) 匹配的代数算法。

有三个着重关注的问题：

(1) 三度图的图同构问题 lec2~4。原论文下载。

(2) 可并行的 (i.e. \(\text{quasi-NC}\)) 二分图完美匹配构造一组解的问题 lec5~7。原论文地址。

(3) 同构问题相关的交互式证明协议。

前置知识：线性代数、群论。

定义 一张图 \(G = (V, E)\)，\(V\)：点集，\(E \subseteq \binom V2\)：边集。其中 \(\binom V2\) 表示从 \(V\) 中选出两者构成的集族。\(|V|\) 称作 \(G\) 的 order，\(|E|\) 称作 \(G\) 的 size。

定义 生成子图 \(G' = (V, E'), E' \subseteq E\)；导出子图 \(G' = (U, E'), U \subseteq V, E' = \{\{i, j\} \mid i, j \in U, \{i, j\} \in E\}\)。\(G\) 是二分图如果 \(\exists V = L \uplus R\)，使得 \(\forall e \in E, e = \{l, r\}, l \in L, r \in R\)。其中 \(\uplus\) 表示不交并。\(G\) 不连通如果 \(\exists V = L \uplus R, \forall e \in E, e \subseteq L\) or \(e \subseteq R\)。

定义 \(M \subseteq E\) 是一个匹配，如果 \(\forall v \in V\)，\(\exists\) 至多一个 \(e \in M\)，使得 \(v \in e\)。\(M\) 是一个完美匹配，如果把至多改为恰好。

定义 \(G = (L \uplus R, E)\)，对 \(S \subseteq L\), 定义 \(N(S) = \{v \in R \mid \exists u \in S, \{u, v\} \in E\}\)。如果 \(|S| > |N(S)|\)，称 \(S\) 是 \(L\) 的一个 shrunk subset。

定理 (Hall) \(G\) 拥有完美匹配当且仅当 \(G\) 没有 shrunk subset。

定义 \(G = (V, E)\)，对 \(S \subseteq L\)，令 \(o(S)\) 为删掉 \(S\) 与其相邻边后的图 \(G[V\setminus S]\) 的奇数大小连通块的个数。如果 \(|o(S)| > |S|\)，称 \(S\) 是 \(V\) 的一个 obstruction。

定理 (Tutte) \(G\) 拥有完美匹配当且仅当 \(G\) 没有 obstruction。

上面两个定理说明了完美匹配问题 \(\texttt{PM} \in \text{NP} \cap \text{co-NP}\)，也即，判断一个图是否拥有完美匹配和是否没有完美匹配都是 \(\text{NP}\) 的。当然，我们知道，\(\texttt{PM} \in \text P\)。比如在二分图上的增广路（或称匈牙利）算法，一般图上的带花树算法。

下面介绍一种代数做法。这种做法在过程上更简洁，且可并行化。

定义 \(A = (a_{ij}) \in M(n, \mathbb F)\)，即 \(A\) 是一个在 \(\mathbb F\) 上的 \(n\) 阶方阵。其行列式为

定理 (Lovász) \(G\) 为二分图。令 \(X_G = \begin{cases}x_{ij} && \{i, j'\} \in E \\ 0 && \text{otherwise}\end{cases}\)。则 \(G\) 有完美匹配当且仅当 \(\det(X_G) \neq 0\)。

其中 \(x_{ij}\) 为互相独立的不定元。也就是说，\(\det(X_G)\) 是一个（不超过） \(|E|\) 元 \(|V|\) 次多项式，\(\in \mathbb Q[x_{ij}]\)。这样的 \(X_G\) 称作 symbolic matrix。

证明按照行列式的定义是显然的，因为每一项和一个匹配一一对应。但是这相当于把所有问题甩给了如何测试 \(\det(X_G) \neq 0\)。其结果会有指数多项。

我们可以很快想到一个随机做法。关键点在于一个 \(d\) 阶多项式 \(f\) 的零点只有至多 \(d\) 个。

引理 (Schwartz-Zippel) \(f\in \mathbb F[y_1, y_2, \ldots, y_m]\) 是一个 \(d\) 阶多项式，那么 \(\text{Pr}_{a_1, a_2, \ldots, a_m \in [2d]^m}(f(a_1, a_2, \ldots, a_m) = 0) \leq \frac 12\)。其中 \(\mathbb F[y_1, y_2, \ldots, y_m]\) 表示在数域 \(\mathbb F\) 上的 \(m\) 元多项式，\([2d]\) 表示 \(\{1, 2, \ldots, 2d\}\)。

而行列式是可以高效并行计算的（高斯消元无法做到这一点）。详见 Lecture 5。

更一般地，我们关心如下问题 (Symbolic Determinant Identity Testing, \(\mathtt{SDIT}\))

Input：给定不定元 \(x_1, \ldots, x_m\) 和一个矩阵 \(X\)，使得 \(X_{ij} = x_k\) or \(a \in \mathbb Q\)。

Output：是否有 \(\det(X) = 0\)？

我们有以下结果：(a) \(\mathtt{SDIT}\) 有高效的多项式时间随机做法（Schwartz-Zippel）。(b) \(\mathtt{SDIT}\) \(\in \text P\) 则 algebraic version of \(\text P \neq \text {NP}\)。

\(\mathtt{SDIT}\) 的更多讨论详见 Lecture 7。

定义 称 \(G = (V, E)\) 和 \(H = (W, F)\) 同构，如果存在一个双射 \(f:V \in W\) 使得 \(\{v, v'\} \in E\) 当且仅当 \(\{f(v), f(v')\} \in F\)。图同构问题 (\(\mathtt{GI}\)) 即判断两张图是否同构。

定理 \(\mathtt{GI} \in \text{NP} \cap \text{co-AM}\)。

证明详见 Lecture 8。

定理 (Babai, 2015) \(\mathtt{GI}\) 可在 \(\exp(O(\log^3 n))\) 解决。

在之前，\(\mathtt{GI}\) 最好的算法是 \(2^{\sqrt n} = \exp(\tilde O(n))\)，其中 \(\tilde O(n)\) 表示 \(\{n\log^c n\}\)。这一步的跨越是巨大的。

有两种切入 \(\mathtt{GI}\) 的方式：组合 (combinatorial) 和群论 (group-theoretic)。组合做法着重考虑图的性质而群论做法着重考虑同构映射的性质。

组合的一个想法是，考虑从一对对应点开始染色，其他点暂时无色。之后每次把一个点变成它周围点的 multiset，然后为每一种不同的 multiset 分配一个颜色作为下一轮的颜色。这样做上若干轮后，到所有颜色的类都固定了，我们也就找到了一个同构，或在操作中途发现其不同构。这个过程叫做 Weisfeiler-Leman 过程。

定理 (Cai-Fürer-Immerman) 存在一对不同构的图，无法在 \(k\) 轮内被区分，而 \(k = O(n)\)。甚至可以是一对三度图，即所有点度数均为 \(3\) 的图。

所以这个组合方法是行不通的。

接下来我们介绍三度图上的群论做法。

定理 (Luks) 对两个三度图 \(G, H\)，存在多项式时间的同构测试算法。

Lecture 2

首先我们来看看群论是如何应用到 \(\texttt{GI}\) 上的。

定义 \(G = (V, E)\)，其自同构集合 \(\text{Aut}(G) = \{f:V \to V \mid {v, v'} \in E \Leftrightarrow \{f(v), f(v')\} \in E\}\)。

很显然地，\(\text{Aut}(G)\) 是一个群。\(\text{Iso}(G, H)\) 不是群，是 \(\text{Aut}(G)\) 的一个陪集。

接下来的一个问题是，对 \(n\) 个点的图，其对称群的一个子群 \(S \leq \text{Sym}(V)\) 的大小是指数级的，该如何存储它？

定理 对 \(T \subseteq P\)，\(\exists T\) 使得 \(\langle T \rangle = P, |T| \leq \lceil \log_2 |P|\rceil\)。

证明是显然的，考虑 \(T_0 = \{1\}\)，每次随便加入一个在 \(P\) 而不在 \(\langle T_i \rangle\) 里的元素，得到 \(T_{i+1}\)，根据 Lagrange 定理可知 \([\langle T_{i+1}\rangle, \langle T_i \rangle] \geq 2\)，因此至多只需要 \(\log_2 |P|\) 次包含整个 \(P\)。

因此，今后提到的所有的关于某个对称群的子群的问题，我们全部可以用其生成元集合进行存储、运算。

接下来我们将图同构问题归约到图自同构问题。后者有更好的代数性质。

考虑如果 \(G, H\) 都是连通的，那么构造一个大图把两者的点边全部包含，找到这个大图的自同构群，然后仅把那些交换了 \(G, H\) 位置的生成元留住。如果不连通，根据同构关系的传递性，对 \(G\) 的每一个连通块枚举 \(H\) 的连通块，如果找到同构的连通块，就把两者划掉，继续剩下的部分。

于是我们的任务便是图自同构问题。这个问题可以基于置换群算法的一个框架。

• 给定一个 \(P \leq \text{Sym}(U)\) 的生成集合，有如下问题
  • Membership 给定 \(\sigma \in \text{Sym}(U)\)，是否有 \(\sigma \in P\)？
  • Order 计算 \(|P|\)。
  • Point Stabilizer 对 \(v \in U\)，计算 \(P_v = \{\sigma \in P \mid \sigma(v) = v\}\)。
  • Set Stabilizer 对 \(W \subseteq U\)，计算 \(P_W = \{\sigma \in P \mid \sigma(W) = W\}\)。

Membership 是可以归约到 Order 的。因为可以通过把 \(\sigma\) 放到生成集合里看 order 有没有变大。

其中，Membership, Order, Point Stabilizer 是简单的，详见 Lecture 4。Set Stabilizer 是难的，Luks 说明了当 \(|P|=p^k\)，其中 \(p\) 是质数时，是简单的。

命题 图自同构问题可以归约到 Set Stabilizer 上。

证明 考虑对于 \(G = (V, E)\)，\(U = \binom V2\)，\(P = \langle \sigma_{i, j} \mid \forall k, (i, k) \leftrightarrow (j, k)\rangle\)，即交换点 \(i, j\) 时，与其相关的所有边交换。那么 \(P_E\) 便是 \(\text{Aut}(G)\)。

命题 三度图的同构问题可以归约到三度图的自同构问题。

证明 考虑枚举一对边 \(e = \{a, b\} \in G, e' = \{a', b'\} \in H\)，建立两个新点 \(v, v'\)，连接 \((v, a), (v, b), (v, v'), (v', a'), (v', b')\)。令 \(f = (v, v')\)。这样新图还是一个三度图，且 \(\text{Aut}\) 中保留了 \(f\)，即 \(\text{Aut}_f\) 中，交换了 \(v, v'\) 的所有元素便是 \(\text{Iso}_{e \leftrightarrow e'}(G, H)\)。那么 \(\text{Iso}(G, H) = \bigcup_{e'} \text{Iso}_{e \leftrightarrow e'}(G, H)\)。

命题 (Tutte) \(|\text{Aut}(G)_f| = 2^l\)。

证明 既然已经有了一个固定物 \(f\)，考虑数学归纳法。

定义 \(G_1 = (\{v, v'\}, f)\)，\(G_{i+1}\) 为 \(G_i\) 加上相邻边与相邻点构成的图。则 \(\text{Aut}(G_1)_f = 2\)。若 \(\text{Aut}(G_i) = 2^j\) 已成立，考虑 \(\text{Aut}(G_{i+1})\)。令

即把 \(\alpha\) 限制在 \(V(G_i)\) 上得到的导出映射。那么 \(\pi_i\) 是一个群同态。所以 \(|\text{Aut}(G_{i+1})_f| = |\text{Im}(\pi_i)| |\text{Ker}(\pi_i)|\)，根据归纳假设，\(\text{Im}(\pi_i)\) 只能是 2-group，接下来考虑 \(\text{Ker}(\pi_i)\)，也就是那些把 \(G_i\) 不变的映射。这些映射只会改变 \(V(G_{i+1}) \setminus V(G_i)\)，如果两个这里的点拥有相同的在 \(V(G_i)\) 中的邻居，那么这两个点可以互换。而 \(V(G_{i+1})\) 内的连边是在 \(G_{i+2}\) 里考虑的，所以现在不用在乎。那么如果有大于两个在 \(V(G_i)\) 中拥有相同的邻居，那么由于每个点度数只有三，这些邻居不可能还能提前在 \(G_i\) 中。所以能互换的只是许多对点。所以 \(\text{Ker}(\pi_i) \cong \mathbb Z_2^k, |\text{Ker}(\pi_i)| = 2^k\)。

在 Lecture 3 中我们会说明为什么在这样的群下 Set stabilizer 是好做的。

接下来，我们考虑如何计算出 \(\text{Aut}(G)_f\)。

上述的群同态是一个限制 (restrict)，因此 \(\text{Im}(\pi_i)\text{Ker}(\pi_i) = \text{Aut}(G_{i+1})_f\)。其中 \(GH = \{gh \mid g \in G, h \in H\}\)。换句话说，两部分独立（在一般的商群中，这一点并不成立）。如果我们能够求出 \(\text{Im}(\pi_i), \text{Ker}(\pi_i)\) 的一组生成元，那么 \(\text{Aut}\) 的生成元可以通过 \(\bigcup_{g \in G} gH\) 得到。有关两个陪集的并的计算问题详见 Lecture 3。

我们已经充分讨论了 \(\text{Ker}(\pi_i)\) 的结构，可知其是（在同构的意义上）若干个 \(\mathbb Z_2\) 的直积。

接下来考虑 \(\text{Im}(\pi_i)\)。并不是所有 \(\text{Aut}(G_i)_f\) 的元素都可以扩展到一些 \(\text{Aut}(G_{i+1})_f\) 中的元素。这是因为我们并没有考虑 \(E(G_{i+1}) \setminus E(G_i)\) 所造成的额外限制。考虑令 \(A = V(G_i) \cup \binom {V(G_i)}2 \cup \binom {V(G_i)}3\)，即 \(G_i\) 的一二三元集合，

令

其中 \(\exists !\) 表示存在唯一。

那么 \(\sigma \in \text{Aut}(G_i)_f\) 应该稳定化 \(A_1, A_2, A'\)。即 \(\sigma(A_1) = A_1, \sigma(A_2) = A_2, \sigma(A') = A'\)。

也就是说，当我们考虑 \(\text{Im}(\pi_i)\) 的时候，\(V(G_{i+1}) \setminus V(G_i)\) 变成了无标号的。我们需要考虑的只有边的个数关系。

所以，我们的问题变为了，给定一个群 \(P \leq \text{Sym}(A)\)，\(A\) 中每个点有一个颜色。我们需要计算 \(P' \leq P\)，使得 \(P'\) 稳定化每种颜色。

由于 \(A'\) 和 \(A_1, A_2\) 是两种不同的对 \(A\) 的划分方式，我们得到了 \(A\) 的如下划分

（实际上绿色是空集）

定义 有色集合自同构问题 (colored set automorphism)

Input: \(P \leq \text{Sym}(A)\) 的生成元集合，其中 \(A\) 是一个标有颜色的集合。

Output: \(\{\sigma \in P \mid \sigma \text{ preserves colors}\}\) 的生成元集合。

在这里，我们还有特殊性质：\(P\) 是一个 2-group。

Exercises for Lectures 1 and 2

Exercise 1. 令 \(H \leq G\)，\(|G| = n, |H| = m, l = \frac nm\)。我们称 \(R = \{g_1, g_2, \ldots, g_l\} \subseteq G\) 是左陪集代表元集合，如果 \(g_iH, i \in [l]\) 访问了所有的 \(H\) 的左陪集。右陪集同理。证明存在一个集合 \(R \subseteq G\) 既是左陪集代表元集合，又是右陪集代表元集合。

Exercise 2. 如果 \(\sigma\) 有长度为 \(l_1, l_2, \ldots, l_k\) 的环，用 \(n\) 和 \(k\) 表示 \(\operatorname{sgn}(\sigma)\)。

Exercise 3. 证明一般图图同构测试可以归约到二分图图同构测试。

Exercise 4. 证明图同构问题可以归约到 colored set automorphism 问题，此时输入没有 2-group 的限制。

Exercise 5. 我们考虑测试 \(G = (V, E)\) 与 \(H = (W, F)\) 的同构性，\(G\) 是随机图，\(H\) 是任意的，\(|V| = |W| = n\)。也即，\(G\) 中每条边都有 \(\frac 12\) 的概率存在。我们接下来试图设计一个算法 \(A\)，使得对至少 \(1 - \frac 1n\) 比例的 \(G\)，\(A\) 能对任意的 \(H\) 测试 \(G\) 和 \(H\) 的同构性。

1. Individualisation step 令 \(l = \lceil 3 \log n \rceil\)，设置 \(l\) 种不同的颜色 \(1, 2, \ldots, l\) 给 \(G\) 中 \(l\) 个不同的结点。我们考虑一一枚举这 \(l\) 个点在 \(H\) 中的像。
   • 像有多少种可能？
2. Refinement step 令 \(U \subset V\) 表示没有被染色的结点。取 \(u \in U\)，考虑 \(u\) 与染了色的结点的相邻关系，可以得到一个长度为 \(l\) 的 01 串 \(b_u = (b_u(1), \ldots, b_u(l)) \in \{0, 1\}^l\)：如果 \(u\) 与第 \(i\) 种颜色相邻，\(b_u(i) = 1\)，否则为 \(0\)。
   • 证明在 Individualisation step 后，\(\mathrm{Pr}[\exists u, u' \in U, b_u = b_{u'}] \leq \frac 1n\)。
3. 基于上述，设计一个我们希望的算法，写出算法过程、复杂度分析、正确性证明。
4. 改造算法，使其时间复杂度能够克服 Individualisation step 中的枚举的开销，达到 \(\text{poly}(n)\)。

Solution 1. 考虑一张二分图 \(G = (L \uplus R, E)\)，\(L\) 对应左陪集，\(R\) 对应右陪集，\(E = \{(gH, Hg) \mid g \in G\}\)。这张图是正则图。所以存在完美匹配。

Solution 2. 一个长度为 \(l\) 的环可以通过 \(l-1\) 次对换还原。\((1\ 2\ \ldots \ l) = (1\ l)\ldots (1\ 3)(1\ 2)\)。所以 \(\text{sgn}(\sigma) = (-1)^{n - k}\)。

Solution 3. 对于一个一般图 \(G = (V, E)\)，考虑构造一张二分图 \(B = (L \uplus R, E)\)。\(|L| = |E|, |R| = |V|, E = \{(e, u) \mid u \in e\}\)。则测试 \(G, G'\) 的同构性等价于测试 \(B, B'\) 的同构性。因为如果有双射 \(\varphi:V \to V'\) 使得 \(e = (u, v) \in E \Leftrightarrow e' = (\varphi(u), \varphi(v)) \in E'\)，那么取 \(\tau(e) = e'\)，\((\tau, \varphi)\) 是一个 \((L, R)\) 到 \((L', R')\) 的同构。同理，如果有双射 \((\tau, \varphi):(L, R) \to (L', R')\) 使得 \((u, v) \in E' \Leftrightarrow (\varphi(u), \tau(v)) \in E\)，那么 \(\varphi\) 是一个 \(V'\) 到 \(V\) 的同构。

这里有一个小问题，就是 \(L' \uplus R' \to L \uplus R\) 的双射不一定是 \(L' \to L, R' \to R\)，有可能有一些 \(\in L'\) 的映射到了 \(R\) 中。这样的点和边首先是是若干个连通块，其次每个点度数都是 \(2\)，因此是若干个环，从而一定是同构的。

Solution 4. 令 \(S = V \cup E \cup E^\perp\)，其中 \(E^\perp = \binom V2 \setminus E\)。将 \(V, E, E^\perp\) 赋予颜色 \(0, 1, 2\)。令 \(P\) 为

也就是说，交换两个点，同时交换边，同时交换边的补。

Solution 5.

1. \[\frac{n!}{(n-l)!} \]

3. 做完 Individualisation 和 Refinement step 后，枚举 \(l\) 个关键点的所有在 \(H\) 中的像，之后对 \(H\) 做 Refinement step。如果不 \(\exists u, u' \in U, b_u = b_{u'}\)，并且不 \(\exists u, u' \in U', b_u = b_{u'}\)，那么检查 \(\{b_u \mid u \in U\}\) 是否等于 \(\{b_u \mid u \in U'\}\)，如果相等，我们可以构建一个同构。如果不能找到这样的双射，直接声明他们是不同构的，因为上文已经保证这种情况下误判的概率 \(\leq \frac 1n\)。

4. 考虑不要枚举所有的关键点的像，而是一个一个将他们确定。

   • 第一轮，我们选择一个关键点 \(u_1\)，寻找其在 \(H\) 中的像 \(v_1\)。由于我们采取的是组合做法，此时能够起到判定作用的，只有度数，也即不知道相邻的点的任何信息而只知道与其相邻。期望与其度数相同的点数为

     \[n2^{-n} \frac{n!}{k!(n-k)!} \leq n2^{-n} \frac{n!}{\left(\frac n2 \right)^2} \sim n2^{-n} \frac{\sqrt n \left(\frac ne \right)^n}{\left(\sqrt n\left(\frac n{2e}\right)^{\frac n2}\right)^2} = O(\sqrt n) \]

     第二步用了斯特林公式。

   • 第二轮，我们选择另一个点 \(u_2\)，但是现在，我们可以做类似于 Refinement step 的操作，将 \(H\) 的点分为两类，第一类是与 \(v_1\) 相邻的，第二类是与 \(v_1\) 不相邻的。此时我们要求 \(v_2\) 对每一个类的度数都要等于 \(u_2\) 的。期望与其在两类中度数都相同的点数为

     \[n \left(\frac 1{\sqrt{\frac n2}}\right)^2 = O(1) \]

   • 继续这个过程，直到我们找到了 \(l\) 个点。

   这样的复杂度是 \(\text{poly}(n)\) 的。

   我们可以有更好的优化：当运行了 \(4 + o(1)\) 轮后，如果进行后面的轮时还有 \(>1\) 种合法的 \(v_k\)，直接随机声明其同构/不同构。因为这种情况的发生概率是 \(o(\frac 1n)\)。

   在第 \(k\) 轮，我们把点划分为 \(2^k\) 个集合，这样的复杂度是 \(O(n \min(n, 2^k))\)。

   我们可以继续优化：在第 \(k\) 轮时沿用第 \(k-1\) 轮的结果。因为每次划分总是一个加细。

   这样复杂度便可以做到 \(O(n^2)\)，与输入同阶。

   Acknowledgement: djq_cpp.

Lecture 3

我们再来重新描述一遍现在的问题。\(P \leq \text{Sym}(A)\) 是一个 2-group，\(A = A_1 \uplus A_2 \uplus \ldots \uplus A_c\)，计算 \(Q = \{\sigma \in P \mid \sigma(A_i) = A_i\}\)。\(P, Q\) 都以生成集合的方式存在。

我们知道，\(p\)-group 的一个重要性质就是 Sylow's theorem。

定理 (Sylow) 若 \(|G| = p^l \cdot s\)，\(p \not| s\)，则 \(G\) 存在阶数为 \(p^i\)（\(1 \leq i \leq l\)）的子群。

这说明 \(G\) 有着平缓的格结构。我们尝试用递归来解决问题。

一个观察是，如果 \(P\) 不 transitive，我们可以对每个轨道单独解决。

定义 \(P \leq \text{Sym}(A), B \subseteq A\)，称 \(B\) 在 \(P\) 是稳定的，如果 \(\forall \sigma \in P, b \in B\) 都有 \(\sigma(b) \in B\)。\(B\) 是一个轨道，如果 \(B\) 是极小的稳定集合。\(P\) 是 transitive 的，当且仅当其没有非平凡稳定集合。

命题 所有轨道构成一个 \(A\) 的划分。

但实际上我们只需要的是

• 对内稳定
• 对外构成划分

这样我们就可以将问题分为两部分，其中第一部分可以递归处理。所以我们的递归条件可以比轨道更松。

定义 \(P \leq \text{Sym}(A)\) 是 transitive 的，\(B \subseteq A\)，\(B\) 是其一个块 (block)，当且仅当 \(B \neq A, B \neq \emptyset\)，且 \(\forall \sigma \in P, \sigma(B) = B \text{ or } \sigma(B) \cap B = \emptyset\)。\(P\) 是 primitive 的，当且仅当其没有大小 \(>1\) 的 \(P\)-block。

命题 若 \(B\) 是一个块，则 \(\{\sigma(B) \mid \sigma \in P\}\) 构成了 \(A\) 的一个划分，称作块系统 (block system)。\(P\) 在 \(\{\sigma(B)\}\) 上有一个导出作用 (induced action)，也即一个定义在 \(\{\sigma(B)\}\) 上的 \(P'\)，满足 \(P'(B) = P(B)\)。

于是可以递归解决 \(P'\) 上的问题。

定义 一个块系统是 minimal 的，如果其对应的导出作用 \(P'\) 是 primitive 的。

由于一个 \(P\) 上的块系统和对应的 \(P'\) 在 \(\{\sigma(B) \mid \sigma \in P\}\) 上的块系统进行复合可以得到一个每个块更大的系统，因此 primitive 说明这里的 "minimal" 表示的是块数最少。而如果是 maximal 就表示块大小最小。

现在我们来简单研究块系统的结构。

命题 \(P\) 是一个 transitive 但不 primitive 的群，\(B\) 是其一个块，\(b \in B\)，那么有 \(P_b \leq P_B \leq P\)，且 \([P:P_B] = |\{\sigma(B) \mid \sigma \in P\}|, [P_B:P_b] = |B|\)。

这是轨道-稳定化子定理的简单应用。

命题 \(P \leq \text{Sym}(A)\) 且 transitive，\(b \in A\)，那么如果 \(\exists K, \text{ s.t. } P_b < K < P\)，那么 \(\exists B\) 是一个块，且 \(b \in B \subset A, |\{\sigma(B) \mid \sigma \in P\}| = [P:K], |B| = [K:P_b]\)。

证明 令 \(\{\sigma_1P_b, \ldots, \sigma_sP_b\}\) 是 \(P_b\) 在 \(K\) 中的陪集，\(s = [K:P_b]\)，那么令 \(b_i = \sigma_i(b), B = \{b_1, \ldots, b_s\}\) 是一个满足条件的块。因为若 \(\sigma(B) \cap B \neq \emptyset\)，考虑 \(b_i = \sigma(b_j)\)，则 \(\sigma = \sigma_i \sigma_j^{-1}\)，从而对任意 \(b_k\)，都有 \(\sigma((\sigma_i^{-1} \sigma_j\sigma_k) \cdot b) = b_k\)，找到 \(\sigma_i^{-1} \sigma_j \sigma_k\) 在哪个陪集里即可。从而 \(\sigma(B) = B\)。

同时我们可以知道，\(K \subseteq P_B, |K| = |P_B|\)，故 \(K = P_B\)。这也就是说，块结构和包含了至少一个 \(P_b\) 的子群结构是对应的。这就像“保证所有操作的区间交不为空”那种 OI 题一样。

为了进一步加深这里的印象，我们再回顾一下轨道-稳定化子定理。

定理 (轨道-稳定化子, orbit-stabilizer) 令 \(G\) 是一个作用在有限集合 \(X\) 上的群，\(\text{Orb}(x)\) 表示 \(x\) 的轨道，\(G_x=\{\sigma(x) = x \mid \sigma \in G\}\)，则有 \(|\text{Orb}(x)|=[G:G_x]\)。

证明 考虑定义 \(\phi_x:G \to \text{Orb}(x), \phi_x(g) = g \cdot x\)，那么 \(\phi_x\) 是一个满射，且 \(\phi_x(g) = \phi_x(h)\) 当且仅当 \(g^{-1}h \in G_x\)。因此存在一个良定义的双射 \(G/G_x \to \text{Orb}(x), gG_x \to g \cdot x\)。由此可推得原命题。

也就是说，虽然 \(K\) 看起来只是单方面得到了 \(B\)，从而 \(K \subseteq P_B\)，但同时也立刻包含了所有的 \(P_B\)。因为如果有一些元素 \(g'\) 在 \(P_B\) 而不在 \(K\) 中，那么 \(g' \cdot x = g \cdot x\) 就会生成新的 \(g'g^{-1} \in P_b\)，但是由于我们已经选取了全部的 \(P_b\)，这是不可能的。所以 \(P_b < K\) 是重要的。

于是我们可以得到

引理 \(P \leq \text{Sym}(A), |A| > 1, |P| = p^l\)，那么 minimal \(P\)-block system 有 \(p\) 个块。

证明 考虑导出作用 \(P'\)，作用在 \(A' = \{\sigma(B) \mid \sigma \in P\}\) 上。如果 \(|A| = p^t, t \geq 2\)，那么任取 \(b \in A'\)，有 \([P:P_b] = p^t\)，根据 Sylow 定理，存在 \(P_b < K < P\)，与 \(P'\) 是 primitive 的矛盾。

这不仅为我们提供了平缓的递归过程，也让 base case 变得 trivial。

接下来我们形式化这个想法。

定义 \(C_B(Q) = \{\forall b \in B, b \sim \sigma(b) \mid \sigma \in Q\}\)，表示 \(Q\) 中保持 \(B\) 中颜色的集合。

首先，我们要看如何将两个子问题的结果合并。

命题 \(C_B(Q \cup Q') = C_B(Q) \cup C_B(Q'), C_{B \cup B'}(Q) = C_B(C_{B'}(Q))\)。

证明是显然的。

需要注意的是，我们并没有保证 \(Q\) 是一个群。因为在 block system 这里，每个块被表示为 \(\sigma \cdot B\)，所以 \(Q\) 需要支持是一个陪集。

引理 若 \(C_B(\sigma P) \neq \emptyset\)，则其是 \(C_B(P)\) 的一个陪集。也就是说，\(C_B\) 内的陪集可提出（代表元可能会变）。

证明 由于 \(B\) 在 \(P\) 是稳定的，\(C_B(P)\) 是一个群。任取 \(\alpha \in C_B(\sigma P)\) 我们想要证明 \(C_B(\sigma P) = \alpha C_B(P)\)。

• \(\alpha C_B(P) \subseteq C_B(\sigma P)\): 任取 \(\beta \in C_B(P) \subseteq P\)，\(\alpha \beta \in \sigma P\)。\(\forall v \in A, v \sim \beta(v) \sim (\alpha \beta)(v)\)，因此 \(\alpha \beta \in C_B(\sigma P)\)。
• \(C_B(\sigma P) \subseteq \alpha C_B(P)\): 任取 \(\gamma \in C_B(\sigma P), \alpha^{-1} \gamma \in C_B(P)\)，这是由于 \(\alpha, \gamma \in C_B(\sigma P)\)。因此 \(\gamma = \alpha(\alpha^{-1} \gamma) \in \alpha C_B(P)\)。

接下来我们开始描述递归过程。

问题

• 输入：\(P \leq \text{Sym}(A)\)，一个 \(2\)-group。\(B \subseteq A\)，满足在 \(P\) 稳定，\(\sigma \in \text{Sym}(A)\)。
• 输出：\(C_B(\sigma P)\)。
• 初始条件：\(B = A, \sigma = id\)。

基于轨道的递归

如果 \(P\) 在 \(B\) 上不 transitive，\(B = B_1 \cup B_2\)，其中 \(B_1, B_2\) 在 \(P\) 稳定，那么 \(C_B(\sigma P) = C_{B_1}(C_{B_2}(\sigma P))\)。

如何测试 \(P\) 在 \(B\) 是否 transitive？我们可以用一个 \(|B| \log |P|\) 的朴素算法。

基于块的递归

对于 \(2\)-group，其 minimal \(P\)-block system 一定形如 \(B = B_1 \cup B_2\)。那么 \(P\) 就形如 \(H \cup \tau H\)，其中 \(H = P_{B_1} = P_{B_2}\)，\(\tau\) 满足 \(\tau(B_1) = B_2, \tau(B_2) = B_1\)。

还有一个问题，就是结果的两侧都是 \(C_B(H)\) 的一个陪集，而我们已经知道它们的并是 \(C_B(P)\) 的一个陪集。

因为 \(\alpha, \beta \in C_B(\sigma P)\)，所以 \(C_B(\sigma P) = \alpha C_B(P) = \beta C_B(P), \alpha^{-1} \beta \in C_B(P)\)。因此 \(\langle C_B(H), \alpha^{-1} \beta \rangle \subseteq C_B(P)\)，所以有

同时显然地，

故两者相同。

那么该如何找到 \(B_1, B_2\) 呢？

命题 (Sims) 在 \(P\) 下，最小的包含元素 \(a, b\) 的块是其在图 \(G = (B, E = \{\sigma(a), \sigma(b)\mid \sigma \in P\})\) 中的连通块。

证明不难。被放在了 Exercises 中。

那么重复执行这个操作，我们就可以得到一个 minimal block system，而上文已经保证了这样的块系统一定是只有两个块的。

Base case

\(|B| = 1\)，其只包含一个 \(b\)，\(P(B) = B\)。\(C_B(\sigma P) = \begin{cases}\sigma P && \sigma(b) \sim b \\ \emptyset && \text{otherwise}\end{cases}\)。

复杂度分析

设 \(f(s)\) 表示 \(|B| = s\) 时最多的递归调用次数。

基于轨道的递归，有

基于块的递归，有

base case

经过简单推导，有 \(f(s) \leq s^2\)。

Lecture 4

我们如果回顾上述过程，会发现还有一点没有解决，就是在 \(P = H \cup \tau H\) 时，如何计算出这样的 \(H\)。更一般地，我们想解决这样的问题：

Input: 给定 \(P = \langle T \rangle \leq \text{Sym}(A), H\) 是 poly-index, poly-recognizable 的（i.e. \([P:H] = \text{poly}(|A|)\)，给定 \(\sigma \in \text{Sym}(A)\) 可以在 \(\text{poly}(|A|)\) 测试是否有 \(\sigma \in H\)）。

Output: \(H\) 的生成元集合。

在我们面对的情况中，\([P:H] = 2, H\) 稳定了 \(B_1, B_2\)，所以是 poly-index, poly-recognizable 的。

考虑这样一个过程：将 \(P\) 生成元集合中的每个元素依次加入，维护两个集合 \(X, Y\)，\(Y\) 表示 \(H\) 的生成元集合，\(X\) 表示 \(H\) 在 \(P\) 的陪集代表元集合。最初 \(X = \{id\}, Y = \emptyset\)。每次考虑 \(\sigma \in T\)，对 \(X\) 中的每个元素 \(\tau\)，测试 \(\tau^{-1}\sigma\) 是否在 \(H\) 中，若有则将其加入 \(X\)，否则将 \(\sigma\) 加入 \(Y\)。

这样我们便得到了一个能够生成 \(H\) 的集合 \(Y\)。但它不是极小的。这可能会影响复杂度。因此我们需要一些处理。

我们知道，\(X\) 的大小永远是固定的，等于 \([P:H] = \text{poly}(|A|)\)。如果我们能够找到一些 \(H_0 = H \geq H_1 \geq H_2 \geq \ldots \geq H_k = id\)，使得 \([H_i:H_{i+1}] = \text{poly}(|A|)\)，那么我们总是可以将其陪集部分提出，从而对整个 \(H\) 进行分解。

这样的 \(H_i\) 显然是存在的。令 \(H_i\) 表示 \(H\) 中固定了 \(\{1, 2, \ldots, i\}\) 的元素，则根据轨道-稳定化子定理有 \([H_i:H_{i+1}] \leq n-i\)。

这样的过程叫做 Sims sifting algorithm。我们再来重新描述一下其要求。

令 \(P=\langle T \rangle \leq S_n\) 是我们要进行 sifting 的群，即对

计算 \(P_i\) 在 \(P_{i-1}\) 中的陪集 \(C_i\)。其中 \(P_i\) 表示 \(P\) 中固定了 \(\{1, 2, \ldots, i\}\) 的元素。

若完成，有

• 每个 \(\tau \in P\) 都可以写为 \(\tau_1 \tau_2 \ldots \tau_{n-1}\)，其中 \(\tau_i \in C_i\)。
• 对每个 \(\sigma \in S_n\)，我们可以测试是否有 \(\sigma \in P\)，通过
  • 对每个 \(\tau_1 \in C_1\)，测试是否有 \(\tau_1^{-1} \sigma\) 稳定了 \(1\)。如果没有，\(\sigma \notin P\)。
  • 如果有，将其送到下一层，测试是否有 \(\tau_2 \in C_2\) 使其稳定了 \(2\)，以此类推。
• \(|P|=|C_1||C_2|\ldots |C_{n-1}|\)。
• poly-index, poly-recognizable 问题的解决。因为这个过程能够去重。
• 特别地，Point Stabilizer \(P_a \leq P\) 可被求出。

现在来重新描述一遍算法流程。

最初我们构建一个 \(n \times n\) 的列表

列表的每个位置要么为空，要么是一个元素。第 \(i\) 行的所有元素构成了 \(C_i\)。\((i, j)\) 中的元素保证稳定化 \(\{1, 2, \ldots, i - 1\}\) 且将 \(i\) 送到了 \(j\)。所以 \(B\) 是上三角的。

sifting 过程如下：对于一个元素 \(\sigma\)，从 \(i=1\) 到 \(n-1\)，执行如下过程

• 在第 \(i\) 行，如果 \(\not \exists \tau, \text{ s.t. } \tau(i) = \sigma(i)\) （i.e. \(B_{i, \tau(i)}\) 为空），则令 \(B_{i, \tau(i)} = \sigma\)。

  否则 \(\sigma \leftarrow \tau^{-1} \sigma\)。可知此时新的 \(\sigma\) 稳定了 \(i\)，因此稳定了 \(\{1, 2, \ldots, i\}\)，故可以送到下一行。

但并不是我们将 \(P\) 的生成元集合一一 sift 就结束了（否则 \(B\) 如何能包含 \(\frac 12 n(n-1)\) 个元素？\(B\) 中的元素并不要求生成无关）。

定理 当

• \(\forall \gamma \in T\)，sift \(\gamma\) 不会改变 \(B\)。
• \(\forall \tau_1, \tau_2 \in B\)，sift \(\tau_1 \cdot \tau_2\) 不会改变 \(B\)。

时，\(C_i\) 为 \(P_{i+1}\) 在 \(P_i\) 的陪集。

证明

如果 \(\sigma = \gamma_1 \gamma_2 \ldots \gamma_s, \gamma_i \in T\)，我们需要证明 \(\sigma\) 能被写成 \(\tau_1 \tau_2 \ldots \tau_{n-1}, \tau_i \in C_i\)。而每个 \(\gamma_i\) 已经能够写成这样的形式了。所以我们要做的，是不断进行交换和合并，类似于冒泡排序。不过有一点要注意的是这些元素并不 commute，我们做的是替换，起到类似交换的效果。

考虑 \(\sigma = \alpha_1 \alpha_2 \ldots \alpha_t, \alpha_i \in B\) 是把 \(\sigma = \gamma_1 \gamma_2 \ldots \gamma_s, \gamma_i \in T\) 中的每个 \(\gamma_i\) 用 \(\in B\) 的元素替换后的结果。\(t = O(|A|^2)\)。

对于相邻两项 \(\alpha_k \cdot \alpha_{k+1}\), \(\alpha_k\) 在第 \(i\) 行，\(\alpha_k\) 在第 \(j\) 行，如果

• \(i < j\)，不做任何事。
• \(i = j\)，由于它们俩是陪集代表元，直接相乘没法直接合并成一个第 \(i\) 行的元素。但是我们知道 \(\alpha_k \cdot \alpha_{k+1}\) 稳定化 \(\{1, 2, \ldots, i - 1\}\)，所以可以写成 \(\beta \cdot \gamma\)，其中 \(\beta \in C_i, \gamma \in P_i\)，注意 \(P_i\) 是由 \(C_{i+1}C_{i+2} \ldots C_{n-1}\) 构成的。
• \(i > j\)，\(\alpha_k \cdot \alpha_{k+1}\) 稳定化 \(\{1, 2, \ldots, j - 1\}\)，所以可以写成 \(\beta \cdot \gamma\)，其中 \(\beta \in C_j, \gamma \in P_j\)。

我们考虑按照 \(j\) 从小往大处理，这样这个过程一定会停止。最终得到的便是一个严格上升的序列，因此符合我们的要求 \(\tau_1 \tau_2 \ldots \tau_{n-1}\)。所以我们只需要 \(\forall \gamma_i \in T, \gamma_i\) 被 \(B\) 识别以及 \(\forall \alpha_k, \alpha_{k+1} \in B, \alpha_k \cdot \alpha_{k+1}\) 被 \(B\) 识别即可。也就是我们上面提的条件。

由此我们可以在 \(O(|A|^6)\) 完成 \(B\) 的构建。参考代码。

由此，我们正式地做完了三度图上的图同构问题。

接下来插入一段张量同构的内容。从第五讲开始我们回到匹配问题。

我们知道矩阵的相似：给定 \(A, B \in M(n, \mathbb F)\)，问是否存在 \(L, R \in GL(n, \mathbb F)\)，使得 \(LAR = B\)。其中 \(M\) 表示矩阵群，\(GL\) 表示满秩矩阵群。

\(3\)-tensors 是把矩阵的二维数组变为了三维。其可以写成一个矩阵列表的形式。

令 \(\overline A = (A_1, \ldots, A_l), \overline B = (B_1, \ldots, B_l), A_i, B_j \in M(n \times m, \mathbb F)\)，定义

• 左作用：\(L \cdot \overline A = (LA_1, \ldots, LA_l)\)。
• 右作用：\(\overline A \cdot R = (A_1R, \ldots, A_lR)\)。
• 线性组合：\(T = (t_{ij})\)，\(\overline A^T = (A_1', \ldots, A_l'), A_i' = \sum_{j=1}^l t_{ij}A_j\)。

经过这三种作用，且 \(L/R/T\) 均可逆的张量与原张量同构。

命题 图同构可以在多项式时间内归约到张量同构。

命题 (Li-Qiao-Wigderson-Wigderson-Zhang) 二分图同构可以在多项式时间内归约到张量同构。

我们在这里只证明后者。

证明 \(B = (U \uplus V, E), U = [n], V = [m], |E| = l\)，构造一个张量 \(\overline A = (A_1, \ldots, A_l), A_i \in M(n \times m, \mathbb F)\)，\(A_e = [\delta_{ij}]\)。

则有 \(B_1 \cong B_2 \Leftrightarrow \overline A_1 \cong \overline A_2\)。

\(\Rightarrow\) 是显然的。\(\Leftarrow\) 考虑如果 \(\overline A_1\) 经过 \(L, R, T\) 得到 \(\overline A_2\)，由于 \(L, R\) 是可逆的，那必然存在 \(\sigma, \tau \in S_n\)，使得 \(\forall i, L(\sigma(i), i) \neq 0, \forall j, R(j, \tau(j)) \neq 0\)，那么 \(L\overline A_1 R(\sigma(i), \tau(j)) \neq 0\)。由于 \(T\) 可逆，考虑 \(\overline A_2^{T^{-1}} = L\overline A_1 R\) 是 \(\overline A_2\) 的矩阵的线性组合，而每一个矩阵只有一个位置有值。因此 \(L\overline A_1 R\) 在一个位置有值则 \(\overline A_2\) 在一个位置有值。因此 \(\overline A_2\) 便是那些 \((\sigma(i), \tau(j))\) 组成的矩阵，这说明 \((\sigma, \tau)\) 是一个 \(B_1\) 到 \(B_2\) 的同构。

接下来我们介绍图同构在密码学中的一个应用：Goldreich-Micali-Wigderson 零知识协议。

目标：Alice 想要验证 Bob 的身份。

Bob 准备了一个随机图 \(G\)，一个随机的排列 \(H\)，令 \(H = \pi(G)\)。私钥为 \(\pi\)，公钥为 \(G, H\)。任何不知道 \(\pi\) 的人无法同时验证 \(G\) 和 \(H\)。我们以此来设计一个协议。步骤如下

• Bob 生成一个随机排列 \(\sigma\)。令 \(K = \sigma(H)\)，向 Alice 发送 \(K\)。
• Alice 根据 \(K\) 向 Bob 随机发送一个 \(0\) 或 \(1\)。
• 如果 Bob 收到了 \(0\)，令 \(\tau = \sigma\)，否则令 \(\tau = \sigma\pi\)，向 Alice 发送 \(\tau\)。
• Alice 检查，如果发送了 \(0\)，是否有 \(K = \tau(H)\)；如果发送了 \(1\)，是否有 \(K = \tau(G)\)。

如果图同构问题是难被破解的，一个不知道 \(\pi\) 的人是无法同时给出 \((K, \tau)\) 使得它们既能符合 \(H\) 又符合 \(G\) 的。因此 Alice 有 \(\frac 12\) 的概率拒绝一个假身份的人。

零知识性：Alice 并不需要知道 \(\pi\) 便可以验证 \(\pi\)。

这个协议不是安全的。因为图同构问题容易被破解。解决方法是将其改为张量同构。

近期的进展：

(Xiaorui Sun) \(q^{O(n^{1.8})}\) （在 \(\mathbb F_q\) 上）。之前的成果是 \(q^{n^2}\)。

(Li-Qiao) 在平均情况下 \(q^{O(n)}\)。

对于应用密码学，取 \(n=14, q\) 是一个 \(12\)-bit 质数 (Matrix Equivalence Digital Signature, MEDS)。

Exercises for Lectures 3 and 4

这个 Exercises 应该是四次中最难的一次了。大概是因为这两讲也就是最难的两讲了。

Exercise 1. 回顾 Sims 给出的算法。

• 命题 (Sims) 在 \(P\) 下，最小的包含元素 \(a, b\) 的块是其在图 \(G = (B, E = \{\sigma(a), \sigma(b)\mid \sigma \in P\})\) 中的连通块。

请证明它。

Exercise 2. 令 \(P \leq \mathrm{Sym}(A)\)，\(B \subseteq A\)，\(|A| = n, |B| = s\)，设计一个算法，使其可以在 \(2^{O(s)} \mathrm{poly}(n)\) 计算 \(\mathrm{Stab}_P(B) := \{\sigma(B) = B \mid \sigma \in P\}\)。（提示：动态规划）

Exercise 3. 我们尝试将三度图扩展到每个点度数 \(\leq 5\) 的图。

1. 证明度数 \(\leq 5\) 的连通图且固定一对边 \(e, e'\) 的同构测试问题可以归约到 \(\leq 5\) 的连通图且固定一条边 \(e\) 的自同构问题。
2. 同三度图那样，我们定义 \(G_i = (V_i, E_i)\)，\(V_i\) 表示那些与 \(e\) 的距离 \(\leq i\) 的点，\(E_i\) 表示那些与 \(e\) 的距离 \(\leq i\) 的边。\(\pi_i:\text{Aut}_e(G_{i+1}) \to \text{Aut}_e(G_i)\) 表示限制 \(\sigma \in \text{Aut}_e(G_{i+1})\) 到 \(G_i\) 上的同态。证明 \(\ker \pi_i\) 是 \(S_c, c \leq 4\) 的直积，证明 \(\text{Aut}_e(G)\) 是 solvable 的。
   （一个方法如下：通过数学归纳法，使用 Jordan-Hölder 定理将这个问题归约到 \(S_c, c \leq 4\) 上，并说明 \(S_4\) 是 solvable 的）
3. 证明计算 \(\text{Aut}_e(G)\) 的问题可以归约到 \(P\) 是 solvable 的 colored set automorphism 问题上。也就是说，你需要定义一个集合 \(A\)，以及一些它的子集对它的划分，使得 \(\sigma \in \text{Aut}_e(G_i)\) 可以扩展到 \(\sigma' \in \text{Aut}_e(G_{i+1})\) 当且仅当 \(\sigma\) 稳定化这些子集。
4. 那么剩下的便是解决 \(P\) 是 solvable 的 colored set automorphism 问题。我们有一个群论结论

• 引理 \(Q \leq \text{Sym}(B)\) 是一个 solvable, primitive 的群，那么存在常数 \(d\) 使得 \(|Q| \leq |B|^d\)。

  设计一个算法，分别讨论在 intransitive, transitive, base case 下如何操作。简要解释为什么你的做法是 \(\mathrm{poly}\) 的。

Solution 1. 如果 \(\{a, b\}\) 和 \(\{\sigma(a), \sigma(b)\}\) 的交不为空，那么它们必须在同一个块里。使用归纳法，我们可知 \(\{a, b\}\) 所在的块必须包含 \(A\)。并且我们知道 \(A\) 是一个块，因为如果存在 \(\sigma(A) \neq A\) 且 \(\exists \tau(a) \in A \cap \sigma(A)\)，那么 \(c \in \sigma(A) \setminus A\) 可以通过路径 \(c \to \tau(a) \to a\)，与 \(A\) 是一个连通块矛盾。所以 \(A\) 是极小的。

Solution 2. 考虑 \(f(i, S) = \{\sigma(b_1, \ldots, b_i) = S \mid \sigma \in P\}\)，其中 \(S\) 是 \(B\) 的一个大小为 \(i\) 的子集。我们知道它会是一个陪集 \(\pi \text{Stab}(b_1, b_2, \ldots, b_i)\)，因此可用 \(f(i, S) = \pi\) 来代替其表示这个集合。

令 \(P_i = \text{Stab}(b_1, \ldots, b_i)\)。

现在考虑 \(b_{i+1}\) 的像。我们想要计算 \(\text{Stab}_{P_i}(b_{i+1})\) 的所有陪集，这个是 point stabilizer 问题，可以通过 Sim's sifting 做。

那么便有

陪集的并怎么求上文已经提到过了。

这样的复杂度便是 \(O(2^s \text{poly}(n))\) 的。

Solution 3.

1. 和三度图同样的做法。因为 \(3\) 确实 \(\leq 5\)。

2. 考虑 \(G_i\) 中每个大小 \(\leq 4\) 的点集，有 \(k\) 个 \(G_{i+1} \setminus G_i\) 中的点的邻居是这个集合，那么这里便乘一个 \(S_k\)，\(k \leq 4\)。

   所以 \(\ker(\pi_i)\) 是一些 \(S_c\) 的直积，\(c \leq 4\)。

   \[1 \trianglelefteq \langle (1\ 2)(3\ 4)\rangle \trianglelefteq \langle(1\ 2)(3\ 4), (1\ 3)(2\ 4) \rangle \trianglelefteq A_4 \trianglelefteq S_4 \]

   根据 Jordan-Hölder 定理，我们知道 \(\ker(\pi_i)\) 是 solvable 的。

   而 \(\mathrm{Im}(\pi_i)\) 是一个 solvable group \(\mathrm{Aut}_e(G_i)\) 的子群，因此是 solvable 的。同时 \(\mathrm{Aut}_e(G_{i+1}) \cong \mathrm{Im}(\pi_i)\mathrm{Aut}_e(\pi_i)\)，而后两者都是 solvable 的，因此是 solvable 的。这是因为

   • 引理 solvable group 的子群是 solvable 的。

   • 引理 \(N, G/N\) 都是 solvable 的，那么 \(G\) 是 solvable 的。

3. 令 \(A = V(G_i) \cup \binom{V(G_i)}2 \cup \binom{V(G_i)}3, N:V(G_{i+1}) \setminus V(G_i) \to A\) 表示 \(v\) 在 \(G_i\) 中的邻居集合。

   令

   \[A_k = \{a \in A \mid \exists \text{ exactly }k \text{ elements }v_1, \ldots, v_k \in V(G_{i+1}) \setminus V(G_i), N(v_1) = N(v_2) = \ldots = N(v_k) \} \]
   \[A' = \{\{u, v\} \mid \{u, v\} \in E(G_{i+1})\} \]

   那么 \(\sigma\) 应该稳定化 \(\{A_k, A_k \cap A'\}\)。

4. Intransitive: \(C_{B \cup B'}(\sigma P) = C_B(C_{B'}(\sigma P))\)。

   Inprimitive: 令 \(B = B_1 \cup B_2 \cup \ldots \cup B_k\) 是一个 minimal block system，令 \(H \leq P\) 稳定化 \(B_1, B_2, \ldots, B_k\)。

   \(P = \bigcup_{a \in A} aH\) where \(A \leq \text{Sym}(k)\),

   \[C_B(\sigma P) = \bigcup_{a \in A} C_B(\sigma aH) = \bigcup_{a \in A} C_{B_1}(C_{B_2}(\ldots (C_{B_k}(\sigma aH)))) \]

   我们发现此时 \(A\) 是 solvable, primitive 的，因此根据引理，\(|A| = k^d\)。

   Base case:

   \[C_B(\sigma P) = \begin{cases}\sigma P & \sigma(b) \sim b \\ \emptyset & \text{else}\end{cases} \]

   复杂度：

   \[\begin{aligned} T(n) &= k^{d+1}T\left(\frac nk\right) + \text{poly}(n) \\ T(1) &= \text{poly}(n) \end{aligned} \]

   得 \(T(n) = n^{d+1}\text{poly}(n) = \text{poly}(n)\).

Lecture 5

我们回到匹配问题上。

第一讲中已经介绍了一种随机化的可并行的寻找完美匹配的算法。我们先来解释一下何为并行。

定义 在 \(\mathbb F\) 上的算术电路 \(C\) 是一个有向无环图 \(G = (V, E)\)，满足

• 叶子，即入度为 \(0\) 的点，被标记为 \(x_i\) 或者 \(\alpha \in \mathbb F\)。
• 内点，即不是叶子的点，被标记为 \(+\) 或 \(\times\)，他们的入度 \(\geq 2\)。
• \(\exists !\) 出度为 \(0\) 的点，称为输出门。

\(C\) 的大小为边集的大小，\(C\) 的深度为最长的叶子到终点的简单路径。

高效的并行计算：\(\text{NC}\) (Nick's class), i.e. \(\text{poly}(n)\)-size, \(\text{polylog}(n)\)-depth。

这样，只要有足够多（且 \(\text{poly}(n)\)）的计算单元，我们就可以将相同深度的同时计算，这样时间复杂度只和深度有关。

我们知道完美匹配的并行算法基于行列式的并行算法。所以我们现在来看如何并行计算行列式。

把 \((i, \sigma(i))\) 当作一条边，转化为若干个环的形式。

这么做的好处是，我们把贡献分给了每个连通块。接下来我们可以利用行列式的容斥性质，来让每个连通块之间互不影响（不需要是一个排列），由此可以进行 low-depth 的递推。

定义 一个 clow 是一条路径 \((i_1, i_2, \ldots, i_l, i_1)\)，满足

• \(i_1\) 是最小的。
• \(i_1\) 不在 \(i_2, \ldots, i_l\) 中出现。

\(i_1\) 称作这个 clow 的头。

一个 clow 序列 \(\{C_1, \ldots, C_k\}\) 的条件和属性如下

• \(\operatorname{head}(C_1) < \operatorname{head}(C_2) < \ldots < \operatorname{head}(C_k)\)。
• 所有边的数量和为 \(n\)。
• \(\text{sgn} = (-1)^{n-k}\)。
• 权值为所有权值的乘积。

定理 (Mahajan-Vinay, 1997)

证明 考虑那些没有组成排列的 clow seq，我们想要证明他们被抵消了。根据鸽巢原理，必有一个点被访问至少两次。

考虑从大往小枚举 clow，同一个 clow 里从起点往终点枚举，直到存在某个 clow \(C_i\) 中的点 \(v\) 满足如下条件之一

• \(v\) 在某个 \(C_j\) 里出现过，\(j > i\)。
• \(v\) 在 \(C_i\) 里构成了一个简单子环。

第一种情况，我们知道 \(C_j\) 是简单环，所以可以直接把 \(C_j\) 旋转后插入到 \(C_i\) 中，这样 \(\operatorname{sgn}\) 变号且权值不变。第二种情况，我们把这个简单子环提出作为一个新的 clow 即可，\(\operatorname{sgn}\) 变号且权值不变。

同时我们发现两种情况是对应的。也即给定一个 clow seq \(W\)，存在一个 \(W'\)，使得 \(W\) 在第一种情况中转化为 \(W'\)，\(W'\) 在第二种情况中转化为 \(W\)。因此所有没有组成排列的 clow seq 两两配对全部抵消。

接下来便是考虑用递推算出

设 \(g_{l, u}\) 表示长度为 \(l\)，head 为 \(u\) 的所有 clow 的权值和。

其中 \(W_{l, u, v, w}\) 表示从 \(v\) 到 \(w\) 的长度为 \(l\) 的，且走过的所有结点编号比 \(u\) 大的路径权值和。这个数组的含义类似 floyd，可以 \(O(n^4)\) 预处理。

设 \(f_{l, u, v}\) 表示使用了 \(l\) 条边，第一个 clow 的 head 是 \(u\)，最后一个的 head \(\leq v\) 的权值和。

\(f_{n, 1, n}\) 便为答案。

这样的复杂度是 \(O(n^4)\) 的。会有 \(O(n^3)\) 的做法吗？

关于对它的深度的验证，在 Exercises 里。

接下来便是本课程第二个较大的问题。我们已经有了一个确定是否存在完美匹配的随机化算法。但是如何构造一组解？

我们给每条边设置一个权重 \(w(e)\)。如果最小权完美匹配是唯一的，那么我们可以通过对权重进行编码来得到一个逐条边确定的算法。

令 \(A_{i, j} = \begin{cases}2^{w(e)} && e \in E \\ 0 && e \notin E\end{cases}\).

则 \(\det A\) 的 lowbit (\(\max k \mid (k \in \mathbb N, 2^k | \det A)\)) 就表示那个最小权完美匹配。

我们每次删掉一条边，得到 \(A'_f\)，计算 \(\det A'_f\)，如果它的 lowbit 改变了，那就让 \(f \in M\)。这样得到的 \(M\) 就是最小权完美匹配。

所以现在，我们需要为每条边分配一个边权，使得最小权完美匹配唯一。

这里先给出一个随机化算法。Lecture 6, 7 将给出一个确定性算法。

应该能够意识到，如果边权在比较大的范围内随机，那存在两组边权和相同的完美匹配的概率会很小。我们考虑形式化这件事。

定义 \(X\) 是一个大小为 \(m\) 的基础集合，\(w: X \to [N]\) 是一个权值函数，\(E \subseteq X, w(E) = \sum_{e \in E} w(e)\)，\(\mathcal F \subseteq 2^X\) 是一个集族，成 \(w\) 对 \(\mathcal F\) 是 isolating 的，如果 \(\min_{E \in \mathcal F} w(E)\) 在唯一 \(E\) 上达到。

引理 (Isolation Lemma, Mulmuley-Vazirani-Vazirani) \(w:X \to [N]\) 均匀独立随机时，\(\operatorname{Pr}[w \text{ isolating for } \mathcal F] \geq 1 - \frac mN\)。

证明 考虑如果 \(\exists A, B \in \mathcal F, w(A) = w(B) = \min_{E \in \mathcal F} w(E)\)，任取 \(x \in A \setminus B\)，考虑

那么令 \(\alpha(x) = \min\limits_{E \in \mathcal F, x \notin E} w(E) - \min\limits_{E \in \mathcal F, x \in E} w(E \setminus \{x\})\)，这是一个与 \(w(x)\) 无关的值，且在此时等于它。说明

那么我们在一个二分图里，令 \(X = E, N = 2|E|\)，就可以有 \(\geq \frac 12\) 的概率成功。这样这整个过程就是 \(\text{polylog}(n)\)-depth 的。

Lecture 6

现在我们来介绍一个确定性算法 (Fenner-Gurjar-Thierauf)，用来寻找一组 isolating 的 \(w\)。

我们先来研究 isolating 的完美匹配的组合性质。

令 \(M_1, M_2\) 是两组完美匹配。两者的对称差 \(M_1 \triangle M_2\) 是若干个偶环。

定义 一个环 \(C\) 在图 \(G\) 中是 nice 的，如果 \(C\) 是两个完美匹配的对称差。

命题 \(C\) 是 nice 的 \(\Leftrightarrow\) 将 \(C\) 中的点删去的导出子图拥有完美匹配。

定义 \(G = (L \uplus R, E)\) 是一个拥有完美匹配的二分图，\(C=(v_1, \ldots, v_k)\) 是一个环。\(w:E \to [N]\) 是一个权值函数，\(C\) 在 \(w\) 中的 circulation 为

引理 如果所有的 nice 的环拥有非零的 circulation，那么 \(w\) 对所有完美匹配是 isolating 的。

证明 若 \(C\) 是 \(M_1, M_2\) 的对称差且两者拥有相同的权值，那么 \(C\) 的 circulation 为零。

我们可以解决一个更强的问题，即找到一组 \(w\) 使得所有的环的 circulation 都不为零，而不仅仅是 nice 的环。因为所有 nice 的环的结构显然更难把握。

突破口在于

引理 \(G\) 是一个 \(n\) 个点的图，如果没有 \(\leq r\) 的环，\(r \geq 4\)，那么 \(\leq 2r\) 的环的个数至多有 \(n^4\) 个。

证明 考虑一个 \(\leq 2r\) 的环 \(C = (v_0, v_1, \ldots, v_{l-1})\)，令 \(f = \frac l4\)，取 \(u_0 = v_0, u_1 = v_{\lceil f \rceil}, u_2 = v_{\lceil 2f \rceil}, u_3 = v_{\lceil 3f \rceil}\)，那么不存在第二个环的 \(\{u\}\) 与 \(C\) 相同。因为如果有了，取两个环的 \(u_0, u_1\) 之间的部分就会有 \(\leq r\) 的环。

这个引理，给了我们能够在 \(\text{poly}\) 将问题减小一倍的机会，这样最终的复杂度也会是 \(\text{poly}\)。

我们考虑将每一个环的 circulation 全部乘起来，并使其非零。

构造 \(t\) 组 \(w\)，\(w_j(e_i) = 2^{i-1} \bmod j\)，令 \(Z_j = \prod_{i=1}^s Z_{w_j}(C_i)\) 表示所有环的 circulation 的乘积。钦定 \(w_0, Z_0\) 是不取模的原始值。需要注意的是由于不存在一个 \(w_0\) 的非空子集和为 \(0\)，\(Z_0 \neq 0\)。

可知 \(Z_j \equiv Z_0 \pmod j\)。若 \(\forall 1 \leq j \leq t, Z_j = 0\)，那就有 \(\operatorname{lcm}(1, 2, \ldots, t) \mid Z_0\)，但 \(Z_0 \leq 2^{n^2 s}\)，而当 \(t \geq 7\) 时就有 \(\operatorname{lcm}(1, 2, \ldots, t) > 2^t\)，所以让 \(t \geq n^2s\)，则一定有一个 \(Z_j \neq 0\)。

对于一般的图来说，\(s\) 可能是指数级的。现在我们用上面的引理来让我们每次处理的 \(s\) 在 \(\text{poly}(n)\)。

令 \(E_1\) 表示所有的最小权完美匹配的边集并。

引理 \(G_1 = (V, E_1)\) 的每个完美匹配拥有相同的权值。

证明详见 Lecture 7。

也即，所有 \(G_1\) 里的匹配都是 \(G\) 里的最小权完美匹配。所以 \(G_1\) 中，每个 nice 的环的 circulation 都是 \(0\)。

我们可以在 \(G_0\) 中为所有长度 \(\leq 4\) 的环构造一组权值 \(w_0\)，使得它们的 circulation 均不为 \(0\)。

那么 \(G_1\) 中不存在 \(\leq 4\) 的环，否则与命题矛盾。因此长度 \(\leq 8\) 的环至多只有 \(n^4\) 个，我们为其构造一组权值 \(w_1\)，使得它们的 circulation 均不为 \(0\)。

同理可以构造出 \(G_2, w_2, G_3, w_3, \ldots, G_{k-1}, w_{k-1}\)，使得

• \(G_i= (V, E_i)\)，\(E_i\) 为 \(G_{i-1}\) 在 \(w_{i-1}\) 下的所有的最小权完美匹配的边集并。

• \(w_i\)：所有在 \(G_i\) 中的长度 \(\leq 2^{i+2}\) 的环的 circulation 均不为 \(0\)。

• \(k = \lceil \log_2 n \rceil - 1\)。

那么由于 \(G_{k-1}\) 没有长度 \(\leq 2^{\lceil \log_2 n \rceil}\) 的环，所以其没有任何环，因此完美匹配唯一。

现在考虑所有 \(w_i\) 的笛卡尔积 \(w_0 \times w_1 \times w_2 \times \ldots \times w_{k-1}\) 作为一个新的边权 \(w\)，加减法是逐位加减，比较是优先级从前向后的字典序比较。

如果有一个最小权完美匹配 \(M^*\)，对于其他所有的 \(M\)，\(\exists i < k-1, \text{ s.t. } M \in G_i, M \notin G_{i+1}\)。所以 \(w_i(M) > w_i(M^*), \forall j < i, w_j(M) = w_j(M^*)\)。因此 \(w(M) > w(M^*)\)。故有

命题 \(w\) 是 isolating 的。

我们考虑笛卡尔积的一个充分描述是，找到一个足够大的 \(B\) 作为进制，然后对数字串进行编码。

也即令

而每一个 \(w_i \leq n^2 \cdot s = n^6\)。由于我们需要求许多条边的 \(w\) 的和再做比较，\(B = n^7\) 是一定可以的。

这样，我们就有了 \(O(n^{\log n}) = 2^{O(\log^2 n)}\) 种权值，每种权值有 \(O(\log^2 n)\) 位，使得对每一张二分图，至少有一种权值可以 isolating。

每种权值的构造可以并行。行列式计算也可以并行。

将所有结果收集的深度是 \(O(\log^2 n)\) 的。

所以最终算法的深度是 \(O(\log^2 n)\)，大小是 \(2^{O(\log^2 n)}\) 的，i.e. \(\text{quasi-NC}^2\)。

Exercises for Lectures 5 and 6

这次作业极其简单。

Exercise 1. 对 \((23), (124), (1243)\) 依次做 sifting。

Exercise 2. 令 \(G = (V, E)\) 为一个完全有向图，\(|V| = n\)，边权为 \(a_{i, j}\)。定义 \(D[l, u]\) 为所有长度为 \(l\)，head 为 \(u\) 的 clow 的权值和，写出一个 \(D[l, u]\) 的递归式，使其算术电路是 \(\text{poly}(n)\)-size, \(\text{polylog}(n)\)-depth 的。

Exercise 3. 证明 \(C\) 是 nice 的 \(\Leftrightarrow\) 将 \(C\) 中的点删去的导出子图拥有完美匹配。证明两个完美匹配的对称差是许多 nice 的环的不交并。

Exercise 4. 设计一个算法使其能够计算一个二分图拥有奇数还是偶数个完美匹配。

Exercise 5. 设计一个 \(\text{poly}(n)\)-size 的算术电路。使其能够对 \(k \in [n]\) 计算 \(\mathbb Q\) 上的 \(s_k\)。其中

Solution 1.

Solution 2. 原式就是。

Solution 3.

如果 \(C\) 是两个完美匹配的对称差，那么对于两者，匹配 \(C\) 中的点对应的那些匹配边必然在 \(C\) 的边集里。所以删掉 \(C\) 后，剩下的图仍有一个导出（指其余的完全保留）完美匹配。

如果将 \(C\) 中的点删去的导出子图拥有完美匹配，那么我们可以通过对 \(C\) 上的边从某个点开始一一标号，并选全部奇数/偶数标号的边构造两组完美匹配。

两个完美匹配的对称差的每个点的度数是 \(0\) 或 \(2\)，因此是若干个环。并且我们知道每个环删去之后的导出子图都有完美匹配，因此它们都是 nice 的。

Solution 4.

构造矩阵 \(A\), \(A_{i, j} = 1\) 当且仅当左侧的 \(i\) 向右侧的 \(j\) 有边。

那么 \(\det A\) 的奇偶性就等于完美匹配数的奇偶性。因为

对一个完美匹配 \((u, \sigma(u))\), \(\prod_{i=1}^n A_{i, \sigma(i)} = 1\), 无论 \(\text{sgn}(\sigma)\) 如何，它都会恰好改变 \(\det A\) 的奇偶性。

Solution 5.

令 \(F(l, r) = (x_l + y)(x_{l+1} + y)\ldots (x_r + y)\)，那么

递归是 \(\text{poly}\)-size, \(\text{polylog}\)-depth 的。

多项式乘法可以有一个 \(\text{poly}\)-size, \(O(1)\)-depth 的算术电路。

令 \(G = \sum_{i=0}^m g_ix^i\)，则

\(g_0F, g_1F, \ldots, g_mF\) 是一个数乘一个多项式，可以在一层内完成，并且这 \(m\) 个都可以放在同一层。之后再花一层把它们加起来。

Lecture 7

我们现在来证明

引理 令 \(E_1\) 表示二分图 \(G = (V, E)\) 在权值函数 \(w\) 下所有的最小权完美匹配的边集并，\(G_1 = (V, E_1)\) 的每个完美匹配拥有相同的权值。

它的一个充分描述是

引理 令 \(E_1\) 表示二分图 \(G = (V, E)\) 在权值函数 \(w\) 下所有的最小权完美匹配的边集并，\(G_1 = (V, E_1)\) 不包含 circulation 不为零的环 \(C\)。

一件有趣的事是，Lecture 6 的算法过程并没有用到二分图的任何性质。它只用于保证这个引理的正确性。

我们引入匹配多面体 (matching polytopes) 的概念。

定义 对于一个 \(G\) 的完美匹配 \(M\)，定义其关联向量 \({\bm x}^M \in \mathbb R^m\) 为

定义 完美匹配多面体是所有完美匹配在 \(\mathbb R^m\) 中的关联向量的凸包

其中凸包的代数定义

定义 对集合 \(S = \{u_1, \ldots, u_k\} \subseteq \mathbb R^m\)，其凸包 \(\operatorname{conv}(S) = \left\{\sum_{i=1}^k \alpha_i u_i \mid \alpha_i \geq 0, \sum_{i=1}^k \alpha_i = 1\right\}\)

权值函数可以很自然地推广到这里。

定义 对任意 \(\bm x \in \mathbb R^m\)，定义

那么就有 \(w(M) = w(\bm x^M)\)。同时根据凸多面体的基本性质，也有

因为 \(w\) 是线性函数，而凸多面体上的线性函数的最值点只可能在顶点。

引理 在二分图上，\(\bm x \in \mathrm{PM}(G)\) 当且仅当

其中 \(\delta(v)\) 表示 \(v\) 的相邻边。

也就是说，在这个问题中，整数规划问题和其所对应的线性松弛问题是等价的。我们回顾整数规划的一个定理

定理 设线性规划问题所对应的多面体为 \(P=\{A\bm x \leq \bm b \mid \bm x \in \mathbb R^n_+\}\)，向量 \(\bm b\) 为整数向量，若 \(A\) 为全单模矩阵 (totally unimodular matrix)，即 \(A\) 的任意子阵的行列式均为 \(0,1,-1\)，则 \(P\) 的顶点都是整数点。

证明 多面体的一个顶点可以看作其一些超平面的唯一交点。每个超平面形如把限制中 \(\leq\) 中的一个改为 \(=\)。那么一个顶点便是一个 \(n\) 个未知数，\(n\) 个方程的线性方程组 \(D\bm x^* = \bm b\) 的唯一的解加上一些舍去条件（未被选中的限制）。根据 Cramer 法则，有

其中 \(D_j\) 为用 \(\bm b\) 替换掉 \(A'\) 第 \(j\) 行后的矩阵。由于 \(\bm b\) 是整数向量，\(\det D_j \in \mathbb Z\)。而 \(\det D\) 此时不为 \(0\)，因此只能为 \(1, -1\)。所以 \(x^*_j \in \mathbb Z\)。

震惊！！原来 Cramer 法则真的不是废物！！！

现在我们来验证这里的 \(A\) 是满足的。

证明 我们把线性规划的限制式写出来。

其中 \(\bm x \in \mathbb R^m\)，\(\bm c = (\overbrace{1, 1, \ldots, 1}^{m \text{ times}})^T\)，\(A\) 为关联矩阵，第 \(i\) 列只有第 \(i\) 条边对应的两个顶点为 \(1\)，\(\bm b= (\overbrace{1, 1, \ldots, 1}^{n \text{ times}})^T\)。

当然，我们这里 \(\operatorname{maximize}\) 什么东西不重要。

完美匹配的限制式则为

经典地，我们可以把 \(=\) 改写成 \(\leq\) 并且 \(\geq\)，\(a \geq b\) 改写成 \(-a \leq -b\)。同时把 \(x \geq 0\) 也写进去，这样得到了一个新的 \(A'\)。

考虑 \(A'\) 的一个子方阵，它的每一列只有至多两个 \(1\)。如果有 \(0\) 个，\(\det\) 为 \(0\)；如果有 \(1\) 个，可以归纳到更小的子方阵；如果所有列都有 \(2\) 个，由于一行表示的是一个点的全部信息，将行分为那些左侧点所在的行和右侧点所在的行，由于每一列都是在前者有一个 \(1\)，后者有一个 \(1\)，所以左侧点和右侧点的行和应该相同，\(\det\) 为 \(0\)。因此 \(A'\) 是全单模矩阵。命题得证。

我们回到原命题。现在，假如有一个 circulation 不为零的 \(C\)，考虑推出矛盾。下面的证明与拉格朗日乘子法的 trick 类似，也即，不为零的线性函数正负两个方向必有一边可以走到更小的，因此不会是极值点。

证明 我们试图找到一个多面体的一个点，使得它在所有环 \(C\) 的关联向量的方向上都是内点。这样如果 \(C\) 的 circulation 不为零，正负两个方向必有一边可以让权值变得更小，而只要这个多面体出现了某个权值，由于权值是线性函数，必有一个顶点的权值不大于它，这导致了矛盾。

令

其中 \(\{\bm x_i\}\) 为所有的最小权完美匹配，也即所有的顶点。我们证明这样的 \(\bm x\) 是内点，证明方法是上述的引理。

由于 \(\{\bm x_i\}\) 是所有的最小权完美匹配，而 \(G_1\) 的边是它们的并，所以 \(\forall e, x_e \geq \frac 1t\)。考虑对任意环 \(C = \{e_1, e_2, \ldots, e_p\}\)，令

其中 \(0 < |\varepsilon| \leq \frac 1t\)，这样，

所以 \(\bm y \in \mathrm{PM}(G)\)。那么，

其中的正负号取决于 \(e_1\) 的选取。我们令 \(\varepsilon\) 的符号与其一致。这样如果 \(C\) 的 circulation 不为零，就有 \(w(\bm y) < w(\bm x)\)。这导致了矛盾。

所以，二分图保证了两件事。

• \(A\) 为全单模矩阵。
• \(\bm y\) 的构造。

作业里有两道举一般图上的反例的题。

值得注意的是，我们给定的边权集合 \(\mathcal W\) (\(|\mathcal W| = \mathrm{poly}(n)\)) 是不依赖于 \(G\) 的形态的。我们的命题是对任意 \(G\)，在 \(\mathcal W\) 中存在一个权值函数 \(w\)。

我们可以把 Fenner-Gurjar-Thierauf 视作一个特殊情况的 \(\mathtt{SDIT}\) 的解的构造的确定性算法。

假设我们有一个黑盒子，盒子中有 \(m\) 个 \(n \times n\) 的矩阵 \(A_1, A_2, \ldots, A_m\)，我们的目标是，构造 \(\mathcal W = \{\overline b_1, \overline b_2, \ldots, \overline b_s\} \subseteq \mathbb F^m\)，使得 \(s = \mathrm{poly}(n)\) 且

这样的 \(\mathcal W\) 称作 hitting set。

那么我们便可以把上面的算法当作一种特殊情况。

• (Fenner-Gurjar-Thierauf, 2016) \(A_i = [\delta_{jk}]\)，这是第一讲中 Lovász 给出的定理的形式。

• (Gurjar-Thierauf, 2020) \(\operatorname{rank} A_i = 1\)。

• (Svensson-Tarnawski, 2017) \(A_i = \begin{cases}\delta_{ij} & i < j \\ -\delta_{ji} & i > j \\ 0 & i = j\end{cases}\)，这是 Tutte 多项式，对应了一般图匹配。

太前沿了我们 \(\pmb{\text{quasi-NC}}\)
!!!!!!!!!!!!!!!!

在一般图上，同样类似地可以定义 \(\mathrm{PM}(G)\)，且有

定理 (Edmonds) \(\bm x \in \mathrm{PM}(G)\) 当且仅当

其中 \(\delta(\cdot)\) 表示跨越其内外的边。

最后，我们来看算术电路与 symbolic matrix 的关系。

定义 一个算术式是除了终点的每个结点的出度都为 \(1\) 的算术电路。

或者说，节点构成了一棵树。

给定一个算术式 \(F\)，我们想要求出 \(A_1, A_2, \ldots, A_m\)，使得 \(\det\left(\sum_{i=1}^m x_iA_i\right)\) 是 \(F\) 所计算的。

我们知道行列式是可以解释为图上的路径计数问题的。所以我们可以使用一个中介：algebraic branching programs, ABP。

定义 一个 ABP 是一个带权有向无环图 \(G\)，且

• 存在唯一的起点终点 \(s, t\)。
• 每条边 \(e\) 被标为 \(X \cup \mathbb F\) 中的一个元素 \(l(e)\)。
• 其计算

我们可以先把一个算术式转化为一个 ABP，之后把 ABP 转化为 symbolic matrix。做法并不难，如下。

在 \(B \to A\) 的时候，我们加一条 \(t \to s\)，并给每个点加上自环。这样 \(s \to t \to s\) 和自环是这张图仅有的环。如果我们能保证每条 \(s \to t\) 的路径都是偶数长度，那么计算行列式时，所有 \(\text{sgn}\) 都是正的，后面计算的便是 \(s \to t\) 的路径条数。

Lecture 8

第八节课补全了之前的进度，讲了一些习题以及讲了一个 \(\mathtt{GNI} \in \text{AM}\) 的协议。我们来讲这个协议。

先预习一下计算理论的相关内容。

复杂度类 \(\text{AM}\) 是一类可在多项式时间内被一个 \(\text{Arthur-Merlin}\) 协议判定的判定性问题。

\(\text{Arthur}\) 是一个拥有标准的图灵机和一个随机数生成设备的验证者，\(\text{Merlin}\) 是一个算力无限的但不可信的证明者，验证者需要验证来自证明者提供的信息，从中提取出合法且自认为有价值的。

最简单的协议是复杂度类 \(\text{MA}\)。此时 \(\text{Merlin}\) 向 \(\text{Arthur}\) 发送一个证明，之后两者不再交互。\(\text{Arthur}\) 使用他的设备来验证其正确性。对误差的刻画类似于 \(\text{BPP}\)。\(\text{MA}\) 与 \(\text{NP}\) 的区别仅在于能否使用随机。

定义 一个概率图灵机是一个非确定性图灵机，其基于一个概率分布选择其转移。

形式化地，一个概率图灵机是一个七元组 \(M = (Q, \Sigma, \Gamma, q_0, A, \delta_1, \delta_2)\)，其中

• \(Q\) 是有限的状态集合。
• \(\Sigma\) 是输入字符集。
• \(\Gamma\) 是一个纸带字符集，包含一个表示空的字符 #。
• \(q_0 \in Q\) 是一个初始状态。
• \(A \subseteq Q\) 是一个接受（终止）状态集合。
• \(\delta_1:Q \times \Gamma \to Q \times \Gamma \times \{L, R\}\) 是第一套转移。其中 \(L\) 表示向纸带左侧一格，\(R\) 表示向右一格。
• \(\delta_1:Q \times \Gamma \to Q \times \Gamma \times \{L, R\}\) 是第二套转移。

每一步，图灵机有 \(\frac 12\) 的概率选择第一套转移，\(\frac 12\) 的概率选择第二套。这个选择不依赖于之前的任何选择。这样，即使是相同的串，其多次放入这个图灵机，有可能有些时候被接受了，有些时候没有被接受。为了适应这个问题，我们称一个语言 \(L\) 是被这个图灵机在误差概率 \(\epsilon\) 下被识别的，如果

概率图灵机与拥有一个随机纸带的确定性图灵机等价。下文将使用后者来描述。

现在我们可以定义

定义 复杂度类 \(\text{BPP}\) (Bounded-error Probabilistic Polynomial time) 是一类可在多项式时间内被一个概率图灵机在所有实例误差概率不超过 \(\frac 13\) 下解决的判定性问题。也即，存在确定性图灵机 \(M\) 以及多项式 \(p\)，使得

• 对所有输入，\(M\) 在多项式时间内终止。
• 如果 \(x \in L\)，那么 \(\operatorname{Pr}_{y \in \{0, 1\}^{p(n)}}[M(y) \text{ accepts }x] \geq \frac 23\)。
• 如果 \(x \notin L\)，那么 \(\operatorname{Pr}_{y \in \{0, 1\}^{p(n)}}[M(y) \text{ accepts }x] \leq \frac 13\)。

其中，\(y\) 是使用的随机纸带，长度是多项式级别的，即 \(p\)。

这里 \(\frac 23, \frac 13\) 可以修改为 \([0, \frac 12)\) 中的任何一个数而不会改变其定义出的集合。这是因为我们可以运行 \(k\) 次，如果 \(\text{accept}\) 次数超过了一半，就认作接受，否则拒绝。这样便是 \(k\) 个 i.i.d. 的随机变量 \(\{X_1, X_2, \ldots, X_k\}, P[X_i = 0] = p, P[X_i = 1] = 1 - p\)。令 \(X = \sum_{i=1}^k X_i, \mu = \mathbb E[X] = (1-p)k\)。

其中 \(0 < \delta \leq \frac 12\)，此时 \(e^{-\delta} < (1 - \delta)^{1 - \delta}\)，因此 \(c_\delta < 1\)。所以无论任意接近 \(1\) 的 \(p\) 在常数轮内就可以做出任何 \(p > \frac 12\) 的效果。

定义 复杂度类 \(\text{MA}\) 是一类可在多项式时间内被一个 \(\text{Arthur-Merlin}\) 协议判定的判定性问题，其中这个协议满足仅进行两轮，且证明者先发送信息。也即，存在一个确定性图灵机以及多项式 \(p, q\)，使得对任意输入串 \(x\)，\(|x| = n\)，

• \(M\) 在多项式时间内终止。
• 如果 \(x \in L\)，那么

• 如果 \(x \notin L\)，那么

其中 \(z\) 可以被视为来自 \(\text{Merlin}\) 的证明，证明长度是多项式级别的，即 \(q\)。

定义 复杂度类 \(\text{NP}\) 是一类可在多项式时间内被一个确定性图灵机验证的判定性问题。

定义 复杂度类 \(\text{AM}\) 是一类可在多项式时间内被一个 \(\text{Arthur-Merlin}\) 协议判定的判定性问题，其中这个协议满足仅进行两轮，且验证者先发送其所有随机的结果给证明者，之后证明者发送证明，验证者只能使用这些随机的结果和来自证明者的证明来验证，无法再增加任何随机性。也即，存在一个确定性图灵机以及多项式 \(p, q\)，使得对任意输入串 \(x\)，\(|x| = n\)，

• \(M\) 在多项式时间内终止。
• 如果 \(x \in L\)，那么

• 如果 \(x \notin L\)，那么

很显然地，图同构问题 \(\mathtt{GI} \in \text{NP}\)。这是因为证明者发送一个排列 \(p \in \mathrm{Iso}(G, H)\)，验证者就可以验证。但图非同构问题 \(\mathtt{GNI}\) 就无法通过类似的方法解决，因为证明两张图不同构是相对困难的。

命题 \(\mathtt{GNI} \in \text{AM}\)。

有一个经典的协议，验证者从 \(G, H\) 中随机选取一个，并应用一个随机排列，发给证明者。证明者需要指出这是来自 \(G\) 还是 \(H\)。如果他每一次都指对了，说明 \(G \not \cong H\)。这里使用的是 private coins，即没有把所有随机的结果都发给证明者，因为不能让证明者得知选取的是哪一张图。对此，我们有

定理 (Goldwasser-Sipser, 1986) 所有使用 private coins 的交互式证明同时有一个 public coins 的交互式证明。

所以我们总可以将其改造为符合 \(\text{AM}\) 的一个协议。

接下来是课上介绍的，第二种协议，其原生使用 public coins。

其想法是，考虑

如果 \(G \cong H\)，那么 \(|N(G, H)| = n!\)，否则等于 \(2\cdot n!\)。我们尝试用这个区别来区分。

令 \(S = \operatorname{encode}(N(G, H)^5)\) 表示将五个 \(N(G, H)\) 的元素进行某种编码（i.e. 某个双射），使其的类型为 \(S \subseteq \{0, 1\}^m, m = \text{poly}(n)\)。

令 \(f:\mathbb F_2^m \to \mathbb F_2^k\) 是一个随机函数。

考虑随机变量 \(X = |\{v \in S \mid f(v) = 0\}|\)。那么就有

命题

这样，我们就可以区分一个 \(|S|\) 是小还是大。

令 \(k = \lceil \log(2^2 (n!)^5)\rceil\)

当 \(G \not \cong H\) 时，\(E[X] \geq 4\)。\(G \cong H\) 时，\(E[X] \leq \frac 14\)。

当 \(G \not \cong H\) 时，

当 \(G \cong H\) 时，

因此我们可以设计这样一个协议：

• 需证明 \(G, H\) 不同构。\(|G| = n\)。
• 令 \(k = \lceil \log(2^2 (n!)^5)\rceil, m\) 表示 \(\operatorname{encode}(N(G, H)^5)\) 的长度。
• \(f:\mathbb F_2^m \to \mathbb F_2^k\) 为 public coins。
• \(\text{Merlin}\) 需要给出 \(K_1, \pi_1, \sigma_1, \ldots, K_5, \pi_5, \sigma_5\)，使得

• \(\text{Arthur}\) 有能力检验这三点。如果检验成功，则认为 \(G \not \cong H\)。
• \(G \cong H\) 时，存在合法证明的概率 \(\leq \frac 14\)，\(G \not \cong H\) 时，存在合法证明的概率 \(\geq \frac 34\)。

可见，这是一个符合 \(\text{AM}\) 的协议。

Exercises for Lectures 7 and 8

Exercise 1. 简要说明如何让算术式转化为 ABP 时每条从 \(s\) 到 \(t\) 的路径均为偶数长度。

Exercise 2. 证明在二分图 \(G\) 中每一个完美匹配的关联向量均为 \(\mathrm{PM}(G)\) 的顶点。\(v\) 是一个多面体 \(H\) 的一个顶点，如果存在线性型 \(l\)，使得超平面 \(L = \{l(x) = a \mid x \in \mathbb R^m\}\) 满足 \(L \cap H = \{v\}\)，且 \(\forall p \in H, l(p) \geq a\)。

Exercise 3. 给出一个反例，说明

• 引理 令 \(E_1\) 表示二分图 \(G = (V, E)\) 在权值函数 \(w\) 下所有的最小权完美匹配的边集并，\(G_1 = (V, E_1)\) 的每个完美匹配拥有相同的权值。

在一般图上并不成立。

Exercise 4. 给出一个反例，说明

• 引理 在二分图上，\(\bm x \in \mathrm{PM}(G)\) 当且仅当

在一般图上并不成立。

Exercise 5. 证明

• 定理 (Edmonds) \(\bm x \in \mathrm{PM}(G)\) 当且仅当

   其中 \(\delta(\cdot)\) 表示跨越其内外的边。

的“仅当”一侧。也即证明在 \(\mathrm{PM}(G)\) 中的 \(\bm x\) 满足这些限制。

Solution 1.

对 \(f_1 + f_2\)，如果我们假设子图 \(f_1, f_2\) 满足每条 \(s_{f_1}\) 到 \(t_{f_1}\) 的路径和每条 \(s_{f_2}\) 到 \(t_{s_2}\) 的路径都是偶数长度，那么连边 \((s, s_{f_1}), (s, s_{f_2}), (t_{f_1}, t), (t_{f_2}, t)\) 这样每条 \(s\) 到 \(t\) 的路径长度是偶数。

对 \(f_1 \times f_2\)，令 \(s = s_{f_1}, t = t_{f_2}\)，之后合并 \(t_{f_1}, s_{f_2}\) 为一个点，这样每条 \(s\) 到 \(t\) 的路径长度是偶数。

Solution 2. 对于一个完美匹配，其关联向量为 \(\bm v^*\)，令 \(a_i = \begin{cases}0 & v^*_i = 1 \\ \frac 1{m - n} & v^*_i = 0\end{cases}\)，那么 \(a_i \geq 0, \sum_{i=1}^m a_i = 1, l(\bm v^*) = \sum_{i=1}^m a_iv^*_i = 0\) 并且对于其他点 \(\bm v\)，由于在 \(v^*_i = 0\) 的地方必定有一些权值，所以 \(l(\bm v) > 0\)。

Solution 3. 论文原图

Solution 4. 考虑两个三元环由一条边 \(e\) 相连，两条与 \(e\) 没有公共顶点的边赋权 \(\frac 23\)，其他赋权 \(\frac 13\)。可知其满足条件。但是这张图的完美匹配唯一，并不包含所有边。

Solution 5. (1) (2) 显然是满足的。考虑 (3)，由于 \(|C|\) 是奇数，对于每个完美匹配，必然存在 \(\delta(C)\) 中的一条边满足 \(x_e = 1\)，也就是说，如果我们把 \(C\) 缩成一个点，建立一张图 \(G'\)，那么对于每个 \(G\) 中的完美匹配，\(C\) 在 \(G'\) 中会被连至少一次，\(\sum_e x_e\) 显然不会比 \(C\) 在 \(G'\) 中被连恰好一次的情况更少。而在 \(G'\) 中，有 \(\sum_{e \in \delta(C)} x_e = 1\)。因此对每个完美匹配和 \(C\)，\(\sum_{e \in \delta(C)} x_e \geq 1\)，完美匹配的线性组合亦是如此。

热门相关：洪荒二郎传   我的嫂子   天堂之门福桑莎   未来兽世：买来的媳妇，不生崽   买妻种田：山野夫君，强势宠！