CS170 Efficient Algorithms and Intractable Problems Section11

课程主页：

https://cs170.org/

https://inst.eecs.berkeley.edu/~cs170/fa18/

课程视频：

https://www.bilibili.com/video/BV1wK411g7ck

这次回顾Section 11。

1. Local Search for Max Cut

(a)

因为每步操作会让cut的大小至少增加$1$，而cut的最大值为$|E|$，所以最多循环$|E|$次。

(b)

对于$v\in V$，记

$$\begin{aligned} d_{in}(v)&= \sharp \{ u| (u,v) \in E,u,v\in S或u,v \in T\}\\ d_{out}(v)&= \sharp \{ u| (u,v) \in E,u\in S, v\in T或u\in T,v \in S\} \end{aligned}$$

那么Max Cut为

$$c=\frac{1}{2}\sum_{v} d_{out}(v)$$

注意到对于任意$v$，都有

$$d_{out}(v) \ge d_{in}(v)$$

以及

$$\sum_{v} d_{out}(v) + \sum_{v} d_{in}(v)=2|E|$$

所以

$$\begin{aligned} 2|E| &= \sum_{v} d_{out}(v) + \sum_{v} d_{in}(v)\\ &\le 2\sum_{v} d_{out}(v)\\ &= 4c\\ c&\ge \frac {|E|} 2 \end{aligned}$$

另解：

考虑$S$中内部边$(u,v )$（即$u, v\in S$），根据定义可得，必然存在$p,q\in T$，使得$(u,p),(v,q)$为cut边（否则$u,v$的外部边数量小于内部边），因此$S$中一条内部边至少对应两个cut，同理可得$T$中一条内部边至少对应两个cut边。假设$S$中内部边数量为$a$，$T$中内部边数量为$b$，cut数量为$c$，那么

$$\begin{aligned} a + b + c &= |E|\\ c&\ge 2a\\ c&\ge 2b\\ |E|=a+b+c&\le 2c\\ c&\ge \frac{|E|}{2} \end{aligned}$$

2. Multiway Cut

(a)

取$s=s_i$，构造点$t$，增加边$(s_j,t),j\neq i$，令边的容量为正无穷，那么$F_i$即为$s-t$的最小割。

(b)

根据定义$F^{\star}$中每条边属于两个$F_i^{\star}$，因为每条边的两个端点不可能属于同一个$F_i^{\star}$，否则将其删除即可。

另一方面，显然$|F_i|\le |F_i^{\star}|$。

(c)

$$|F|\le \sum_{i} |F_i| \le \sum_{i} |F_i^{\star}| =2|F^{\star}|$$

剩余部分参考了习题解答。

方案是计算出$F_i$之后，删除元素最多的$F_i$，不妨记为$F_j$，最终得到

$$F=\bigcup_{i\neq j} F_i$$

注意到我们有

$$|F_j|\ge \frac{1}{k}\sum_{i}|F_i|$$

此外，$s_j$和每个$s_i,i\neq j$都不属于同一个元素，所以$F$依然为multiway cut，那么

$$\begin{aligned} |F| &\le \sum_{i\ne j} |F_i| \\ &= \sum_{i} |F_i|- |F_j| \\ &\le \sum_{i} |F_i|- \frac 1 k \sum_{i} |F_i| \\ &= \left(1-\frac 1 k\right)\sum_{i} |F_i| \\ &\le \left(1-\frac 1 k\right) \sum_{i} |F_i^{\star}|\\ &\le \left(2-\frac 2k\right) |F^{\star}|\\ \end{aligned}$$

3. Fast Modular Exponentiation

假设

$$b^c = k_1(p-1) + r_1, 0\le r_1 < p- 1$$

那么根据费马小定理可得

$$a^{b^c} \equiv a^{r_1}\equiv (a\bmod p)^{r_1} \bmod p$$

对于最后一项，利用快速幂可以在$O(\log r_1)=O(\log p )$时间内求出结果。

所以问题转化为求出$r_1$。

假设

$$b = k_2(p-1) + r_2, 0\le r_2 < p- 1$$

那么

$$\begin{aligned} b^c &=(k_2(p-1) +r_2)^c \\ &\equiv r_2^c \bmod (p-1) \end{aligned}$$

利用快速幂可以在$O(\log c)$时间内求出结果。

因此总时间复杂度为

$$O(\max(\log c, \log p))$$

4. Fermat’s Little Theorem as a Primality Test

(a)

def f(p):
    i = 2
    while 1:
        if (i ** (p - 1) % p) == 1:
            print(i)
            break
        else:
            i += 1

f(15)

得到结果

4

验证后不难发现

$$\begin{aligned} 4^{14}&\equiv 1 \bmod 15\\ 2^{14}&\equiv 4 \bmod 15\\ \end{aligned}$$

(b)

假设$b$满足

$$b^{p-1}\equiv 1 \bmod p$$

那么

$$(ab)^{p-1}\equiv b^{p-1}\not\equiv 1 \bmod p$$

对于$b_1\neq b_2$，满足

$$\begin{aligned} b_1^{p-1}&\equiv 1 \bmod p\\ b_2^{p-1}&\equiv 1 \bmod p \end{aligned}$$

那么可以证明

$$ab_1 \not \equiv ab_2 \bmod p$$

这是因为如果该事实不成立，那么必然有

$$p| a(b_1 -b_2)$$

因为$p,a$互素，所以

$$p| (b_1 -b_2)$$

但是$b_1\neq b_2$，并且$b_1 -b_2\in [-(p-2),p-2]$，所以该事实不可能成立。

从而映射$f(b)=ab \bmod p$是单射，将每个通过费马测试的数映射为一个不通过费马测试的数，因此不通过费马测试的数的数量必然大于等于通过费马测试的数的数量。

备注：这里的数属于范围$\{1,\ldots, p-1\}$。

(c)

$a$不一定存在。