高级算法设计
快速排序
python
算法代码
| |
测试代码
| |
rust
注意一下，
rand库需要声明依赖- <=这样的比较需要
PartialOrd的 trait sort()需要实现Ord的 trait，只有整型有；浮点类型只能使用sort_by()去自定义比较函数sort()是原位排序，更加推荐更快的sort_unstable()
算法代码
| |
测试代码
| |
| |
随机算法分类
Las Vegas 算法
随机数对结果正误没有影响，但是对于运行时间有影响（允许最坏情况下不终止）。eg，快排
Monte Carlo 算法
随机数选择会影响是否出错。eg，检验矩阵乘法正确性
上述的定义不关心是否是多项式时间复杂度。考虑现实一般都会加上。
形式化定义
- Zero-error,Probabilistic,Poly(ZPP)，时间的期望为多项式
- $$ \begin{aligned} l\in \mathcal{ZPP} \iff&\exists deterministic\ alg\ A\in \mathcal{P},random\ input\ r,\\ &\{x\in l \iff A(x,r)=1\} \end{aligned} $$
- Randomized Poly 单边出错，假阴性，时间被多项式限制
- $$ \begin{aligned} l\in \mathcal{RP} \iff&\exists deterministic\ alg\ A\in \mathcal{P},random\ input\ r,\\ &\{x\in l \rightarrow Pr(A(x,r)=1)\ge\frac{1}{2},\\ &x\notin l \rightarrow Pr(A(x,r)=0)=1 \} \end{aligned} $$
- Co-RP 单边出错，假阳性
- $$ \begin{aligned} l\in \mathcal{Co-RP} \iff&\exists deterministic\ alg\ A\in \mathcal{P},random\ input\ r,\\ &\{x\in l \rightarrow A(x,r)=1\ge\frac{1}{2},\\ &x\notin l \rightarrow Pr(A(x,r)=0)\ge\frac{1}{2} \} \end{aligned} $$
- $$ \{\bar{l}|l\in\mathcal{RP}\} $$
- Bounded Probabilistic Poly(BPP) 双边出错
- $$ \begin{aligned} l\in \mathcal{BBP} \iff&\exists deterministic\ alg\ A\in \mathcal{P},random\ input\ r,\\ &\{x\in l \rightarrow Pr(A(x,r)=1)\ge\frac{2}{3},\\ &x\notin l \rightarrow Pr(A(x,r)=0)\ge\frac{2}{3} \} \end{aligned} $$
算法的正确率提升
事实上，上述定义中的概率常量不影响（对于$\mathcal{RP}\mathcal{Co-RP}$常数无关，对于$\mathcal{BPP}$错误率小于$\frac{1}{2}$，集合之间等同。独立随机的输入运行多次，然后选择结果。
eg，$\mathcal{RP}_\frac{1}{2}$ 提升到 $\mathcal{RP}_\frac{1}{4}$ ，运行 2 次，至少一次 1 即输出 1，全 0 输出 0。
eg， $\mathcal{BBP}_\frac{1}{3}$ 提升（错误率不能超过 $\frac{1}{2}$）。取独立随机输入$r_1,…r_{2t+1}$ 对应随机变量$Y_1,…Y_{2t+1}$，如果和$Y=\sum Y_i\ge t+1$，输出 1，反之输出 0
$$ \begin{aligned} &Pr(\sum Y_i\le t)\\ &=Pr(Y-E(Y)\le t-E(Y))\\ &\le Pr(Y-E(Y)\le t-(2t+1)\frac{2}{3})\\ &\le Pr(|Y-E(Y)| \ge t/3+2/3)\\ &\le \frac{Var(Y)}{(t/3+2/3)^2}\\ &\le \frac{(2t+1)Var(Y_i)}{(t/3+2/3)^2}\\ &\le \frac{(2t+1)/4}{(t/3+2/3)^2}\\ \end{aligned} $$
t 足够大时，正确的概率即可足够大
Les-Vegas 和 Monte-Carlo 转化
$$\mathcal{RP}\cap\mathcal{Co-RP}=\mathcal{ZPP} $$
- $\mathcal{ZPP}\subseteq\mathcal{RP}$：超时直接输出一个结果，按照$\mathcal{RP}$的要求，给 0（超时概率被 markov 不等式限制，给出 1 一定正确，给 0 可能会出错 ）
- $\mathcal{ZPP}\subseteq\mathcal{Co-RP}$，类似的
- $\mathcal{RP}\cap\mathcal{RP}\subseteq\mathcal{ZPP}$：联立$A_1\in\mathcal{RP} ,A_2\in\mathcal{Co-RP}$,(1,1)输出 1，(0,0)输出 0，(0,1)再来一次。时间期望被正确率控制（(1,0)自相矛盾，不可能发生）
这些算法集合关系如下。注意，$\mathcal{NP}$和$\mathcal{BPP}$之间实际上关系未知，有待进一步证明。目前大概认为不等
自动机
自动机
每次读取下一个字符（有限集$\Sigma$），根据状态转移函数改变状态（有限集$Q$）
$\delta:Q\times \Sigma\to Q$
语言
字符串的集合 $L\subseteq\Sigma^*$
等价定义指示函数 $L:\Sigma^*\to {0,1}$
正则语言
能被自动机接收的语言
有限差异
集合${\sigma|L_1(\sigma)\neq L_2(\sigma)}$有限大小
有限语言都是正则语言。正则语言对于交、并、补运算封闭。
对于两个有限差异的问题$L_1,L_2$，对于$L_1$有复杂度$T(n)$为算法。那么对于$L_2$，总可以把差异部分打表，相同部分调用$L_1$的算法，形成一个$T(n)+n+c$的算法。
- 判定问题 $F:\Sigma^*\to {0,1}$
- 优化问题 $F:\Sigma^*\to \Sigma^*$
- 计数问题 $F:\Sigma^*\to \mathbb{N}$
图灵机
图灵机
根据状态和读入的字符，可以写字符，变状态，左右移动
$F:Q\times \Gamma\to Q\times \Gamma\times\{\leftarrow,\rightarrow\}$
（图灵）可计算问题
起始状态时，带子作为输入字符串。停机之后，带子上字符串作为输出
$F:\Sigma^*\to \Sigma^*$
图灵机是所有编程语言的计算能力。
图灵机线性加速定理
对于一个可计算问题，存在一个图灵机有复杂度$T(n)$算法。那么存在一个图灵机可以实现$\frac{1}{d}T(n)+n+c$的算法。
主要靠扩充状态和字符集，将原先的状态和字符压缩表示。
3-CNF
$$\psi=C_1\wedge C_2…$$
当中子句是 3 元或函数，当中文字为变量的形式$x_i,\neg x_i$：$C_i=l_{i,1}\vee l_{i,2}\vee l_{i,3}$
- 非门: $x=\neg y \iff (x\vee y)\wedge(\neg x\vee \neg y)$
- 或门: $x=(y\vee z)\iff (\neg x\vee y\vee z)\wedge(x\vee \neg y)\wedge(x\vee \neg z)$
作为 3SAT 的基础。而且，对于 4SAT 问题，定义一个新变量$z_i$来表示一个子句$l_{i,1}\vee l_{i,2}\vee l_{i,3}\vee l_{i,4}$，写成$l_{i,1}\vee l_{i,2}\vee z_i,\neg z_i\vee l_{i,3}\vee l_{i,4}$。
非确定性图灵机
non-deterministic Turing machine
非确定性图灵机
根据状态和读入的字符，接下来随机选择状态转移（可以认为是无限度的并行执行，选择最正确的分支作为结果），可以写字符，变状态，左右移动
$F:Q\times {0,1}\to Q\times \Sigma\times\{\leftarrow,\rightarrow\}$
规约
对于规约$\Psi$，有$F(X)=H(\Psi(X))$
如果规约$\Psi$是多项式时间的、$\log$空间、etc；称为多项式时间规约、$\log$空间规约、etc。记为$\le^\text{cost}_{way}$。
- 多项式时间规约：$F\le^\text{poly}_m H\implies p(n)+q(p(n))$，规约时间+H 算法（规约输入）
- 图灵规约：递归调用$H$，adaptive。需要带 oracle 的图灵机（预言机，指的是规约到更强大的预言机来解决）$F\le^\text{poly}_T H\implies p(n)+p(n)q(p(n))$，规约时间+规约出来的状态数目*H 算法（规约输入）
- Truth Table 规约：一次给定多个$H$,non-adaptive
如果$\forall F\in\mathcal{NP}$，$F$可以被规约到问题$H$，称$H$为$\mathcal{NP}-C$问题（NP 完全问题）
图灵可计算问题规约到 bool 线路
对于输入字符串为$n$。图灵机停机用时$T(n)$。那么必然读写头移动范围不超过$T(n)$。可以把图灵机的运行过程用一个$T(n)\times T(n)$的表格表示。每格记为$\Sigma\times (Q\cup{\mathcal{o}})$，表示每格的字符，图灵机状态、读写头是否在本格。即为计算表格。
因此，上述每格的有限数目的状态用$c$个 bit 编码。注意到，任意一个时刻某个位置字符是否改变，必然只取决于上一个时刻其左右 3 个字符的情况（$3c$个 bit）。因此最后可以表达为有限个逻辑门组合。
注意，对于$\mathcal{NP}$问题，对于多项式时间判定函数$R()$的计算表格，也可以类似规约。如此规约出来的问题具有 3CNF 问题的形式。由此也可以证明3SAT 问题是$\mathcal{NP}$完全的。
构件替换规约
对于$A\le B$的规约，由于张量网络结合律，使用 B 的构件，发挥 A 中函数作用。如4SAT 到 3SAT 的规约。
P，NP
判定问题，可以对应一个集合/语言。
$$f:x\to \{0,1\}$$
$$L_f=\left\{x|f(x)=1 \right\}$$
存在多项式时间算法$R$有输入$|y|=|x|^k$，有$F\in\mathcal{NP},F(x)=1\iff \exists y,R(x,y)=1$
Ladner-定理
如果$\mathcal{P}\neq\mathcal{NP}$，存在问题不是 P，也不是 NP 难。
构造一个算法，使得增长速度能够介于$\mathcal{P}$与$\mathcal{NP}$之间。大致思路是，在 SAT 之间插入$n^{H(n)}$的 1，当中$H(n)$是关于$n$的多项式时间函数，且$n$趋于无穷时候趋于无穷。记$SAT_H={\psi01^{n^{H(n)}}:\psi\in SAT \wedge n=|\psi|}$。
#P
函数$F$属于$\#P$问题：存在多项式时间算法$R$，使得$F(x)=|{y|R(x,y)=1}|$（多项式时间验证可解的解的计数）
如果任何$\#P$的问题可以规约到问题 B，B 是$\#P$ 完全（$\#P-complete$）。$\#P-complete$也是$\mathcal{NP}$ 完全的。#SAT 是 $\#P$ 完全的。01Permanent 问题也是$\#P$完全的
CSP
$CSP(\mathcal{F})$ 问题（Constraint Satisfaction Problem）
变量的约束满足形式$\mathcal{F}$，约束是否可以满足的问题
$\mathcal{F}$如果有形式，$CSP(\mathcal{F})$为 P 问题，否则为 NP 难
- 0-valid
- 1-valid
- Horn SAT
- dual Horn SAT
- affine（线性函数）
- bijunctive（2SAT）
3-SAT 作为 CSP 的特例。每个子句相当于 8 种约束中的一种。要求满足所有约束
Holant-#CSP
$Holant(\mathcal{F})$问题
对于张量网络$G$,点上的函数属于$\mathcal{F}$，输出 G 的值
$\#CSP(\mathcal{H})$ 问题（Constraint Satisfaction Problem 计数）
张量网络形如 $=_n,F_i\in\mathcal{H}$ 的二部图
$\#CSP(\mathcal{H})=Holant(\{=_i…\}\cup \mathcal{H})$
对于变量集合$X=\{x_1,x_2,…x_n\}$，有函数 $R_1(x_{1,1},…x_{1,r_1}),…R_m(x_{m,1},…x_{m,r_m})$，函数有$R_i\in\mathcal{F}$。$\#CSP(\mathcal{F})$就是求解
$$\sum_{\sigma:X\to D}\prod R_j(\sigma(x_{j,1}）,…,\sigma(x_{j,r_j}))$$
对于#CSP 问题，其中一部分是$\mathcal{P}$问题，见#CSP 二分定理
二部 Holant 问题
对于两个函数集合$\mathcal{H},\mathcal{F}$，对于二部图$G(U,V,E)$：$U$上函数来自$\mathcal{H}$；$V$上函数来自$\mathcal{F}$ 定义问题$\#\mathcal{H}|\mathcal{F}$，求解张量网络值。也被称为二部 Holant 问题
注意，任何一条边，可以转化成两条连着二元相等关系顶点$=_2$的边。因此，有如下等价关系
- $\#\mathcal{F}\equiv\#\{=_2\}|\mathcal{F}$
- $\#CSP(\mathcal{F})\equiv\#\{=_i,…\}|\mathcal{F}$
- $\#CSP(\mathcal{F})\equiv\#\{=_i,…\}\cup\mathcal{F}$
- 在$\mathcal{F}$直接有两边相连，插入$=_2$
- $=_i$关系相连，转换为一个更大的相等关系
问题的集合和实例的集合不是一回事：
- 从问题角度，#CSP 问题类是 Holant 问题类的子集,$\#CSP(\mathcal{F})=\#\mathcal{F}\cup\{=_i,…\}\subseteq\#\mathcal{F}$
- 对于一个确定的函数集合$\mathcal{F}$，$\#\mathcal{F}$的实例对应的实例$\#CSP(\mathcal{F})\supseteq\#\mathcal{F}\cup\{=_2\}$，前者可规约到后者
算法
矩阵检验
在$O(n^2)$，概率判断两矩阵乘是否相等另一矩阵。重复选择向量$x$。对于 0，1 的 2-bit 矩阵，错误率（在不等情况下）为$\frac{1}{2}$。
$$A(Bx)==Cx$$
GCD
不分解质因数，使用辗转相除法计算最大公因数 GCD。至多 2 次减半，时间复杂度度$O(\ln n*\ln^2 n)$。
辗转相除法的过程中，还可以同时构造得到 Bezout 系数$x,y\in \mathbb{Z}$使得 $GCD(a,b)=x\times a+y\times b$。一个可能的实现如下
| |
素数判定
对于一个大小为 n 的数，注意到表示这个数需要的复杂度是$O(\ln n)$。所以合理的多项式时间算法，应该是针对$\sim \ln n$的多项式。
双边出错算法
给定一个$\mathcal{BPP}$算法
- n 不是不为 2 的偶数
- $n=r^s\qquad r,s>1$
- $r$遍历过$2…\log_2{n}$
- 二分查找$r^s<n$，判断是否成立，时间复杂度$O(\ln^3 n)$，遍历+二分查找+翻倍乘法（FFT）作为基
- 独立随机的取$a_1,a_2,..a_{10}\in[2,n-1]$
对于素数$p$，有$(a^{\frac{p-1}{2}}-1)(a^{\frac{p-1}{2}}+1)=a^{p-1}-1\equiv0\pmod p$。p 至少整除$a^{\frac{p-1}{2}}-1,a^{\frac{p-1}{2}}+1$其中一个。因此必有$a^{\frac{p-1}{2}}\equiv \pm1\pmod p$。对于素数，只有最后两个步骤可能出问题。mod 为+1 的概率为$\frac{1}{2}$，因为原根。
对于合数。
$$ \begin{aligned} \epsilon=Pr(\exists i,&a_i^{\frac{n-1}{2}}\equiv -1\pmod n\\ \forall i,&a_i^{\frac{n-1}{2}}\equiv \pm1\pmod n,\ &a_i^{n-1}\equiv 1\pmod n ) \end{aligned} $$
找一个坏的$y$使得$y^{\frac{n-1}{2}}\neq \pm1\pmod n$。然后 y 和其他的 mod 余数为$\pm1$的乘，即可生成等大小的集合，类似原根里的构造集合 。使得能正确筛出概率$\ge \frac{1}{2}$。坏的$y$在 mod -1 元素存在时（$a^{\frac{n-1}{2}}\equiv -1\pmod n=-1\pmod{PQ}$）必然存在。
分解有$n=p^\alpha Q=P\times Q\implies GCD(P,Q)=1$（分解的存在性由通过第 2 大步保证，Q 是剩下素因子乘积）。使用 中国剩余定理保证下列要求有解。
$$ \left\{ \begin{aligned} &y\equiv 1\pmod{P}\\ &y\equiv a\pmod{Q},\qquad a\neq \pm 1 \end{aligned} \right. $$
而且容易知道，解$y\star$不能是 naive 的 1，-1，否则下列等式总有一行不成立。且等式和在一起必与$y^{\frac{n-1}{2}}\equiv \pm1\pmod n$矛盾（对 n mod $\pm1$，对于 PQ 必然都 mod $\pm 1$两个结果一样，因为$(y\mp 1)\mod n=(y\mp 1)\mod P=(y\mp 1)\mod Q=0$）
$$ \left\{ \begin{aligned} &y\star^{\frac{n-1}{2}}=1^\frac{n-1}{2}=1\equiv 1\pmod{P}\\ &y\star^{\frac{n-1}{2}}=a^{\frac{n-1}{2}}\equiv -1\pmod{Q} \end{aligned} \right. $$
单边出错算法
关于素数$\mathcal{Co-RP}$，关于合数的$\mathcal{RP}$算法。前大部分得出合数都是可靠的。
- n 不是不为 2 的偶数
- $n=r^s\qquad r,s>1$
- $r$遍历过$2…\log_2{n}$
- 二分查找$r^s<n$，判断是否成立，时间复杂度$O(\ln^3 n)$，遍历+二分查找+翻倍乘法（FFT）作为基
- 随机选取$a\in[2,n-1]$
- $GCD(a,n)\neq 1$，合数
- $a^{n-1}\neq 1\pmod{n}$，合数
- $a^{\frac{n-1}{2}}\neq \pm1\pmod{n}$，合数
- $n-1=2^rs$遍历，$a^{2^{r-1}s},…a^s$，mod n，检测结果序列
- 出现$\neq \pm1$，合数
- 出现$1,-1$形式，素数，可能错误选出合数
- 全是 1，素数，可能错误选出合数
注意，$s$ 是奇数，必然的$-1^s\equiv -1\pmod{n}$。和之前合数部分类似的，可以拓展出坏根。出现$\neq \pm1$的概率$\ge \frac{1}{2}$
原根
原根有$a\star ^{\frac{p+1}{2}}\equiv-1\pmod p$。素数必有原根。且原根能满足下列集合在 mod p 意义上的相等
$$p,a\star\implies \{a\star ^1,a\star^2 … a\star ^{p-1}\}\pmod p=\{1,2,3…p-1\}\pmod p$$
假定一个数已知有原根。那 mod 之后，等于 1，-1 的集合等大小（原根乘 mod 余 1 的集合每个元素，构造出来两个集合等大小）。
图完美匹配
对于二部图$G(U,V,E)$，对于其邻接矩阵表示$M$，不存在完美匹配的必要条件为$\det(M)=0$
$$\det(M)=\sum_{\pi\in S_n}(-1)^{sign(\pi)}\prod^n_{j=1}m_{j,z(j)}$$
不是充分条件，因为比如完全的二部图的邻接矩阵，每行每列全为 1，会导致抵消而等于 0。引入$O(n^2)$个变量，保证$\det(M)$行列之间不相消
$$ m_{ij}=\left\{ \begin{aligned} &x_{ij}\qquad (u_i,v_j)\in E\\ &0 \qquad (u_i,v_j)\notin E \end{aligned} \right. $$
此时不存在完美匹配的充要条件即为$\det(M)=M(x_{ij})\equiv0$
使用 Schwartz Zippel Lemma，取素数$n^2\le p\le 2n^2$，独立随机取$r_1,…r_n\in \mathbb{F}_p=[1..p]\subseteq\mathbb{Z}$，在模 p 意义下计算行列式（eg，高斯消元法数值计算，时间复杂度$O(n^3)$）。该算法对于有匹配的图可能给出无匹配的错误结果，单边出错。
$$ \begin{aligned} \epsilon&=Pr(\det(M)=0)=Pr(M(x_{ij})=0)\\ &\le \frac{\deg(M)}{p}\\ &=\frac{n}{n^2}=\frac{1}{n} \end{aligned} $$
SAT
对于 bool 变量$x_1,…x_n$，有逻辑表达式$\varphi=(x_i\vee…)\wedge…$，是否存在一组取值使得$\varphi$可被满足为真。3-SAT 为$\mathcal{NP}$问题。
正分-SAT
逻辑表达式$\varphi=(x_i\vee…)\wedge…$，每个子句满足有正分，反之 0 分。MAX-2SAT 是$\mathcal{NP}$问题。
$$\varphi=(x_1\vee \bar{x}_2)\wedge(\bar{x}_1\vee x_3\vee\bar{x}_4)…$$
考虑变量$y_1,…y_m\in\{0,1\}$，当中$y_i$表示第 i 个 clause 是否被满足。优化目标即为$W=w_1y_1+…w_my_m$。把逻辑表达式转化为约束条件有
$$ \left\{ \begin{aligned} &y_1\le x_1+(1-x_2)\\ &y_2\le (1-x_1)+x_3+(1-x_4)\\ &…\\ &x_i\in\{0,1\}\\ &y_i\in\{0,1\}\\ \end{aligned} \right. $$
问题为 Integer Linear Programming（ILP），为$\mathcal{NP}$。可以把整数约束松弛求近似解（线性规划是$\mathcal{P}问题$），$0\le x_i\le1,0\le y_i\le 1$。由于范围更大，有$opt(\tilde{P})\ge opt(P)$（可以证明$opt(\tilde{P})$必然是一个分数解）。令随机变量$Pr(X_i=1)=x_i^{\star}$，把$opt(\tilde{P})$的结果作为概率去做舍入（可以保持均值/期望不变）
此时，有 clause 的满足也成为随机变量$Y_i$，$R=w_1Y_1+…w_mY_m$
$$ \begin{aligned} \mathbb{E}(R)&=\sum w_iE(Y_i)\\ &=\sum w_iPr(Y_i=1)\\ &=\sum w_i(1-Pr(Y_i=0))\\ &=\sum w_i(1-\prod(Pr(X_i=1/0)))\\ &\ge \sum w_i(1-[\frac{\sum x^{\star}/(1-x^{\star})}{s_i}]^{s_i})\qquad\text{$X_i=1/0$对应概率}\\ &=\sum w_i(1-[\frac{s_i -\sum (1-x^{\star})/x^{\star}}{s_i}]^{s_i})\qquad\text{平均值不等式}\\ &=\sum w_i(1-(1-\frac{y_i^{\star}}{s_i})^{s_i})\qquad \text{注意逻辑表达式} \end{aligned} $$
对于$k\ge2,z\in[0,1]$，有上凸函数$f(z),f(0)=0,f(1)=1-(1-\frac{1}{k})^k \le1-\frac{1}{e}$
$$ \begin{aligned} f(z)&=1-(1-\frac{z}{k})^k>0\\ f^\prime(z)&=(1-\frac{z}{k})^{k-1}>0\\ f^{\prime\prime}(z)&=-\frac{k-1}{k}(1-\frac{z}{k})^{k-2}<0 \end{aligned} $$
上凸函数有函数值大于直线，有$f(z)=1-(1-\frac{z}{k})^k>(1-\frac{1}{e})z$。则$\mathbb{E}(R)\ge \sum w_i(1-\frac{1}{e})y_i^{\star}$。又由于松弛条件$opt(P)\le opt(\tilde{P})=\sum w_iy_i^{\star}$。可以得出估计的偏差可被有效控制住
$$ \frac{\mathbb{E}(R)}{opt(P)}\ge 1-\frac{1}{e} $$
SAT-转换
可以把很多问题归结到 SAT 问题求解。而且 SAT 问题有现成的求解器程序（solver）
图着色编码
如 3-染色问题，每个点的每种染色结果编码为一个 bool 变量$x_{i1},x_{i2},x_{i3}$，然后枚举约束
- 一条边上两个点颜色不同,$\neg x_{i1}\vee \neg x_{j1}$
- 一个点必须有一种颜色 $x_{i1}\vee x_{i2}\vee x_{i3}$
- 不需要指定一个点只取一种颜色（solver 求解之后，再舍去多多余即可，但这可能增加 solver 负担）
logic puzzle
至少一人说谎。$a,b,c$3 个 bool 变量对应 ABC 是否说真话。可以将蕴含转换为析取形式
- A: B is lying.
- B: C is lying.
- C: A and B is lying.
对应表达式
- $a\vee b\vee c$
- $a\to \neg b,\neg a\to b \implies\neg a \vee \neg b,a\vee b$
- $b\to \neg c,\neg b\to c \implies\neg b \vee \neg c,b\vee c$
- $c\to(\neg a\wedge\neg b),\neg c\to \neg(\neg a\wedge\neg b)\implies \neg c\vee \neg a,\neg c \vee \neg b,a\vee b\vee c$
最后可以求解为$\neg a,b,\neg c$
数独
$p(i,j,n)$表示第 i 行 j 列是否取数字 n
- 每行:$\bigwedge_i\bigwedge_n\bigvee_j p(i,j,n)$
- 每列:$\bigwedge_j\bigwedge_n\bigvee_i p(i,j,n)$
- 小方块:$\bigwedge_s\bigwedge_t\bigwedge_n\bigvee_i\bigvee_j p(3s+i,3t+j,n)$
- 一个格子对应一个数:$n\neq n^\prime \implies \neg p(i,j,n) \vee \neg p(i,j,n^\prime)$
推箱子
每个位置对应 3 种状态，Empty,Worker,Box。可以编码 k 步行动（行动可以被行动前后的状态对<pre,con>来编码）的推箱子解。
- 每个状态有且只有值
- 每轮行动要求前一轮之后前提能被满足
- 每轮行动后，状态对应改变
- 状态的改变必然是由于有行动
- 每轮有且只有一个行动
线性规划
线性规划（LP，Linear Programing）。有如下的标准形式。
$$ \min z=\mathbf{c}x\text{ s.t. } \left\{\begin{aligned} Ax=b\\ x\ge 0 \end{aligned}\right. $$
如果要求变量只能取整数，即为 ILP；如果要求一部分为整数，为 MILP。
区间调度
一些工作（持续时间是区间$[s_j,e_j)$），分配给一些工人（工人 t 有$B_t=\bigcap[s_{ti},e_{ti})$的时间段有别的事情）。要求同一个人干活、其他杂事之间都不能重叠。
定义 bool 变量$x_t^j$表示工作 j 分配给工人 t。可以化归为整数线性规划
- $\sum_t x_t^j=1$：有时间的至少有一个人干某个工作 j
- $x_t^i\le(1-x_t^j)$：如果工作 i、j 时间冲突，一个人至多做其中一件事情
- $x_t^j\in{0,1}$
排班
- N 个人
- W 个周数
- D：一周天数
- S 种任务
定义 bool 变量$x_{n,w,d,s}$表示第 w 周第 d 天，第 n 号人是否被分配工作 s
- 优化目标 $\min z=z_1+z_2$
- 尽量整个周末要么加班要么不加班：$z_1=w_1\sum (y_{n,w,1}+y_{n,w,2})$
- 每个人尽量上满天数：$z_2=w_2\sum_n q_n$
- 硬约束
- 每人每天只能干一个工作：$\sum_s x_{n,w,d,s}\le 1$
- 每天每项工作要满足最少人数：$\sum_n x_{n,w,d,s}\ge C_{w,d,s}^{\min}$
- 一些工作不能连续干：$\forall (s_1,s_2)\in\text{forbidden}:x_{n,w,d,s_1}+x_{n,w,d+1,s_2}$
- 软约束
- $\sum_s x_{n,w,6,s}-\sum_s x_{n,w,7,s}+y_{n,w,1}\ge 0;\sum_s x_{n,w,7,s}-\sum_s x_{n,w,6,s}+y_{n,w,2}\ge 0$
- $\sum x_{n,w,d,s}+q_n\ge T_{\min}$
MAX-CUT
对于图$G=U\cup W,U\cap W=\emptyset$，m 条边，使得$|E(U,W)|$最大。这是$\mathcal{NP}$问题。
对于每个顶点取$\frac{1}{2}$分给 U、W，对于每个边，有$\frac{1}{2}$概率(uu,uw,wu,ww)在 cut 中。因此，由于期望的线性性，有
$$ \mathbb{E}(|E(X_u,X_w)|)=\frac{m}{2} $$
而且因为$opt\le m$，因此这是一个$\frac{1}{2}$的估计。
注意到，$\frac{m}{2}=E(Y)=\frac{1}{2}E(Y|X_1=0)+\frac{1}{2}E(Y|X_1=1)$。由于平均数的特性，必然有一个$E(Y|X_1=0),E(Y|X_1=0)$是比原先的期望$E(Y)$更大。可以持续按照$X_1,X_2…$固定，取更大的期望，递降下去，去随机化。这样可以得到 cut 的取值。
具体来说，由于期望线性性，可以把给定$X_1,..X_{i-1}$取值，准备给定$X_i$的某个 0/1 取值时候的 cut 大小的期望表示为：$X_1,..X_{i}$内部的边的期望，$X_1,..X_{i}$与其他未确定点边界处的边的期望，和未确定点内部的边的期望。
$$ \mathbb{E}(Y|X_1,…X_i)=\mathbb{E}(X_1,…X_i)+\mathbb{E}(|X_j,unkonwn|)+\mathbb{E}(unkonwn) $$
容易知道:
- 无论$X_i$的具体取值，$\mathbb{E}(unkonwn)$都是相同的。
- 已知点和未确定点之间边界边的期望有$\mathbb{E}(|X_j,unkonwn|)=\mathbb{E}(|\{X_1,…X_{i-1}\},unknown|)+\mathbb{E}(|X_i,unkonwn|)$。
- $\mathbb{E}(|\{X_1,…X_{i-1}\},unknown|)$被之前确定的点所固定，与$X_i$取值无关
- 而$\mathbb{E}(|X_i,unkonwn|)$关于$X_i$取 0/1 是对称的，因此也和$X_i$取值无关。
因此，事实上该去随机化算法，每次新加入的点，取值使得已确定的点之间能构成最大的 cut 即可。可以考虑下列一些简单的例子。
| 三角形 | u | w | $\mathbb{E}$ |
|---|---|---|---|
| u,w | 2 | 2 | $\frac{2+2}{2}=2$ |
| u,u | 0 | 2 | $\frac{0+2}{2}=1$ |
| 四边形取邻边 | u,u | u,w | w,u | w,w | $\mathbb{E}$ |
|---|---|---|---|---|---|
| u,w | 2 | 2 | 4 | 2 | $\frac{2+2+4+2}{4}=5/2$ |
| u,u | 0 | 2 | 2 | 2 | $\frac{0+2+2+2}{2}=3/2$ |
| 正四面体取邻边 | u,u | u,w | w,u | w,w | $\mathbb{E}$ |
|---|---|---|---|---|---|
| u,w | 3 | 4 | 4 | 3 | $\frac{3+4+4+3}{4}=7/2$ |
| u,u | 0 | 3 | 3 | 4 | $\frac{0+3+3+4}{2}=5/2$ |
注意，这个提升算法因为没有回退，因此可能陷入局部最优解。考虑如下一个简单例子。
| |
局部来看，1，2，3 这三个位置填 w，局部都是最优的多 1 条 cut 边。但是，全局最优要求 w 填在 1 或者 3 的位置（最优解里 cut 大小为 4，否则最后 cut 大小为 3）。
Birthday Paradox
$m$个球，独立随机投入到$n$个盒子。作为生日悖论的推广。还包括如 md5 的 hash 碰撞，服务器负载均衡请求等。$X_i$表示 i 个盒子中球的数目，之间同分布但不独立（和为$m$）。注意有 $x\in(0,1)\implies e^{-x}>1-x$
m~sqrt(n)
$$ \begin{aligned} Pr(\max X_i\ge 2)&=1-Pr(\forall i,X_i\le 1)\\ &=1-(1-\frac{1}{n})(1-\frac{2}{n})…(1-\frac{m-1}{n})\\ &\ge 1-e^{-\frac{1}{n}}…e^{-\frac{m-1}{n}}\\ &=1-e^{-\frac{m(m-1)}{2n}}\\ &\ge 1-e^{-(\frac{m}{\sqrt{2n}})^2} \end{aligned} $$
因此，$m=\Theta(\sqrt{n})\approx\sqrt{2n}$时候，大概率 2 球碰撞（$Pr=1-e^{-1}$）
m~n
$$m=n\implies \max X_i \sim \frac{\ln n }{\ln \ln n}$$
有高概率实现（with high prop，whp，概率量级为$1-o(1)$）。证明有上界下界。如果尝试次数大于 1 次，可以改善到$\Theta(\ln \ln n)$（证明未被提及）
上界
$$ Pr(\max X_i\le 3\frac{\ln n }{\ln \ln n})\ge 1-o(1) $$
$$ \begin{aligned} &Pr(X_1\ge 3s)\\ &=Pr(\exists i_1,…i_{3s}\in [1,n],Ball_{i_j} \in X_1 )\\ &=Pr(\bigcup Ball_{i_j} \in X_1 )\\ &\le \sum Pr(Ball_{i_j} \in X_1)\\ &=\binom{m}{3s}\left(\frac{1}{n}\right)^{3s}\\ &\sim \binom{n}{3s}\left(\frac{1}{n}\right)^{3s}\\ &\le \left(\frac{ne}{3s}\right)^{3s}\left(\frac{1}{n}\right)^{3s}\\ &=(\frac{e}{3s})^{3s}\\ &<s^{-3s}\\ &=(\frac{\ln \ln n }{\ln n})^{3s}\\ &< (\frac{\sqrt {\ln n}}{\ln n})^{3s}\\ &=e^{-\ln \ln n \cdot (\frac{3}{2}\frac{\ln n }{\ln \ln n})}\\ &=n^{-3/2} \end{aligned} $$
$$ \begin{aligned} Pr(\max X_i\ge 3\frac{\ln n }{\ln \ln n})&=Pr(\exists i,X_i\ge 3\frac{\ln n }{\ln \ln n})\\ &=Pr(\bigcup X_i\ge 3\frac{\ln n }{\ln \ln n})\\ &\le nPr(X_1\ge 3s)\\ &\le n^{\frac{1}{2}} \end{aligned} $$
下界
$$ Pr(\max X_i\ge \frac{1}{3}\frac{\ln n }{\ln \ln n})\ge 1-o(1) $$
定义同分布但不独立的随机变量$Y_1,…Y_n$ 有
$$ Y_i=\left\{ \begin{aligned} &1\qquad X_i\ge \frac{s}{3}\\ &0\qquad otherwise \end{aligned} \right. $$
$$ \begin{aligned} Pr(Y_i=1)&=Pr(X_i\ge \frac{s}{3})\\ &\ge Pr(X_i=\frac{s}{3})\\ &=\binom{m}{\frac{s}{3}}(\frac{1}{n})^{\frac{s}{3}}\cdot (1-\frac{1}{n})^{m-\frac{s}{3}}\\ &\sim\binom{n}{\frac{s}{3}}(\frac{1}{n})^{\frac{s}{3}}\cdot (1-\frac{1}{n})^{n-\frac{s}{3}}\\ &\ge (\frac{n}{\frac{s}{3}})^{\frac{s}{3}}(\frac{1}{n})^{\frac{s}{3}}e^{-1}\\ &=(\frac{3}{s})^{\frac{s}{3}}e^{-1}\\ &=(\frac{(3\ln \ln n)}{\ln n})^{\frac{s}{3}}e^{-1}\\ &\ge (\ln n )^{-\frac{s}{3}}e^{-1}\qquad n>4\implies 3\ln \ln n>1\\ &=e^{\ln \ln n\cdot \frac{\ln n}{3\ln \ln n}}e^{-1}\\ &=n^{-1/3}e^{-1} \end{aligned} $$
因此有期望估计为 $E(Y_i)\ge n^{-1/3}e^{-1}$，期望和估计为$E(Y)\ge n^{2/3}e^{-1}$
$$ \begin{aligned} &Pr(\max X_i\ge \frac{1}{3}\frac{\ln n }{\ln \ln n})\\ &=Pr(\exists Y_i=1)\\ &=Pr(\sum Y_i \ge 1)\\ &=1-Pr(\sum Y_i \le 0)\\ \end{aligned} $$
$$ \begin{aligned} Pr(\sum Y_i \le 0)&=Pr(Y\le 0)\\ &\le Pr(|Y-E(Y)|\ge E(Y))\qquad \text{注意到}E(Y)\ge 0\\ &\le \frac{Var(Y)}{(n^{2/3}e^{-1})^2}\\ &\le \frac{nVar(Y_i)}{(n^{2/3}e^{-1})^2}\\ &\le \frac{e^2}{4}n^{-\frac{1}{3}} \end{aligned} $$
注意，这时候虽然$Y_i$之间不独立，但是其负相关（显然），协方差小于 0。和的方差等于方差的和加上负的协方差。因此还是可以使用chebyshev 不等式进行放缩。
m>n
期望里每个盒子的球数目为$\frac{m}{n}$。而在$m\sim n\ln n$量级上，可以保证高概率每个盒子均符合期望。
考虑独立随机变量$Y_1,…Y_m$，$Y_i$表示第 i 个球是否进入 1 号盒子。$E(Y_i)=\frac{1}{n},E(Y)=\frac{m}{n}$。取$m=24 n\ln n$。使用 chernoff-bound 进行放缩
$$ \begin{aligned} &Pr(\forall X_i\in [(1-\frac{1}{2})\frac{m}{n},(1+\frac{1}{2})\frac{m}{n}])\\ &=1-Pr(\exists X_i\notin [(1-\frac{1}{2})\frac{m}{n},(1+\frac{1}{2})\frac{m}{n}] )\\ &\ge 1-nPr(X_1 \notin [(1-\frac{1}{2})\frac{m}{n},(1+\frac{1}{2})\frac{m}{n}])\\ &=1-(Pr(X_1 \le(1-\frac{1}{2})\frac{m}{n})+Pr(X_1\ge (1+\frac{1}{2})\frac{m}{n}))\\ &\ge 1- 2ne^{-\frac{(\frac{1}{2})^2}{3}\cdot\frac{m}{n}}\\ &=1-2ne^{-2\ln n}\\ &=1-2/n=1-o(1) \end{aligned} $$
张量网络
定义
使用$[d]$表示大小为$d$的有限集合。$\mathbb{R}^d$的向量可以视为对每一维上的离散函数$F(i):[d]\to\mathbb{R}$。$k$维张量即可以视为$F(i_1,…i_k)$
张量网络
张量/离散函数作为点、自变量作为边的图。如果函数不对称，需要指定边的次序
图$G(V,E)$中每个点$v$赋予一个$d_v$元函数$F_v$
张量网络的值：$\sum_{e\in [d]} \prod_v F_v(e_{v,1},…e_{v,d_v})$，对所有边取一种赋值之后的结果求和
eg，对于 SAT 问题 ，$\exists {x_1,…x_n}\to {0,1},\bigwedge c()=1 \iff \sum\prod c()\ge 1$（可以引入一些辅助节点，保证出现次数大于 2 次的边，转化成很多条连到辅助节点的边，辅助节点的函数要求所有边取值相同）
| |
$e\in\{0,1\},F_1(0)=1,F_1(1)=3,F_2(0)=2,F_2(1)=5$，网络值是 $1\times 2+3\times 5=17$
eg，3-regular 图（顶点度数均为 3）的 3 染色问题，可以用张量网络和转变为计数问题
引入外边成为多元函数
定义输入$X=\{x_1,…x_n\}\in D^n$，有
$$F_G(x_1,…x_n)=\sum_e\prod_v F_v(e_{v,1},…e_{v,d_v},x_i)$$
eg，$AB_{x_1x_2}=\sum A_{x_1e}B_{ex_2}$
| |
- 矩阵的迹(对角线元素求和)
- $trace(A)=\sum A_{ee}$(自环),$trace(ABC)=\sum A_{e_1e_2}B_{e_2e_3}C_{e_3e_1}$
- 张量积，(克罗内克积)对于矩阵$M_{dd},N_{dd}$，结果为$d^2\times d^2$的矩阵，$M\otimes N=(m_{ij}N)$
- $(M\otimes N)_{x_1x_2,x_3x_4}=M_{x_1x_3}N_{x_2x_4}$ 。结果中行标$x_1x_2$可以视为把$M$的行标$x_1$和$N$的行标$x_2$字符串组合在一起
- 可以表示为
x1-M-x3, x2-N-x4的张量网络（没有内部边，无需求和，顶点函数就是矩阵的 index）
- 张量网络值满足结合律
- 有限域上的线性方程组解集大小，等于对应张量网络值
- $\#P$问题，存在多项式时间算法
- 相同的变量用一个多元相等关系约束
- 每个方程对应一个 $\mod{}$ 顶点
- 图的顶点覆盖数目（选定一组顶点，使得顶点的邻边包括所有的边）
- $\#P-complete$问题
s+t
$s+t$的 bool 函数$F$，输入为$x_1,…x_s,y_1,…y_t$。向左边视为行标，向右边视为列标。对于$2^s\times2^t$矩阵$M_{x_1,…x_s,y_1,…y_t}=F(x_1,…x_s,y_1,…y_t)$。注意如果$s=0$（$t=0$），降级为行（列）向量。此时的张量网络函数可以视为矩阵乘法。
全息规约
$$ AB=AEB=AMM^{-1}B=(AM)\cdot(M^{-1}B) $$
一个$f,h$二分的张量网络，可以先把$f,h$之间插入一个$=_2=[1,0,1]$，然后把$=_2=MM^{-1}$，把$f,h$换一个基：$fM^{\otimes i},(M^{-1})^{\otimes j}h$
对于一个$F，H$二分，而且$F、H$之间每条边上都有顶点$M$的张量网络。有问题间的等价关系$\#\{FM^{\otimes i}\}|\{H\}\equiv\#\{F\}|\{M^{\otimes j}H\}$
对称函数
对于置换$\pi$,对于自变量$\forall x_i$，有
$$ F(x_1,…x_n)=F(x_{\pi(1)},…x_{\pi(n)}) $$
如果是 bool 为自变量的对称函数，可以用$f_i$表示$i$个 1 时候$F$的值。那么$F$可以完全被$f_0,f_1,…f_{n}$来确定。对于 n 元相等关系(全相等时候取 1，否则取 0)，记$F=[1,0,…0,1]$为$=_n$
#CSP-二分定理
bool 定义域的#CSP 问题，其他形式是#P 难的问题
- 01 值域：
- 仿射关系
- 非负实数值域
- pure affine
- product type
- 复数值域
- 第一易解类$\mathcal{A}$
- 第二易解类$\mathcal{P}$，作为 product 形式的推广
#CSP-第一易解类
对于 bool 定义域，值域$\mathbb{C}$的函数$F$。有一个第一易解类$\mathcal{A}$，对于$\#CSP(\mathcal{A})$存在多项式时间算法。定义仿射关系，$\mathcal{X}_{(AX=C)}$，为$D$上$n$维的指示函数。
可以定义一类特殊条件的多项式$P()$：
- 整系数多项式$P(x_1,…x_n)$，整数加法乘法运算
- $P()$最高次数为 2，交错二次项的系数为偶数
那么，$F\in \mathcal{A}$当且仅当$F$具有形式$\mathcal{X}_{(AX=C)}\cdot i^{P(x_1,…x_n)}$
考虑$AX=C$的自由变量有$x_1,…x_r$，其他的变量可以表示为$X^\prime=(x_1,…x_r,1)$的线性组合，$x_j=L_j(X^\prime)\mod 2$。注意到
- $\forall a\in\mathcal{Z},a=0,1\mod2\iff a^2=0,1\mod 4$
- 显然有$a\pmod2=0\iff a^2\pmod4=0$
- $a^2 \pmod4 =1$可知$a^2,a$为奇数
- $a=2k+1\implies a^2=(2k+1)^2=4(k^2+k)+1$,$\mod 1$的情况得证
- 注意到对$i=\sqrt{-1}$的指数，可以在$\mod 4$的意义下计算
因此我们可以把$P()$中的不自由的$x_j$（$j\in[r+1,n]$）进行合法的替换
- 一次项$x_j$替换为$L_j(X^\prime)^2$，因为在$\mod 4$下不改变
- 平方项和交错二次项正常换成$L_j(X^\prime)^2$和$2L_j(X^\prime)L_{k}(X^\prime)$
此时$P(x_1,..x_r,x_{r+1},…x_n)=P(x_1,…x_r,L_{r+1}(X^\prime),…L_{n}(X^\prime))=Q(x_1,…x_r)$，容易验证新的多项式$Q()$仍然满足上述$P()$的条件。因此有
$$ \sum \mathcal{X}_{(AX=C)}\cdot i^{P(x_1,…x_n)}=\sum i^{Q(x_1,…x_r)} $$
接下来进行逐步消除自变量。考虑$x_1$。注意到，$x_i$都是 bool 变量，因此必然有$x_i^2\equiv x_i$，我们可以把关于$x_1$的二次项$\alpha_1x_1^2$（如果存在的话）改写成$\alpha_1x_1$融合进关于$x_1$的一次项当中。
对$x_1$的一次项系数进行分类讨论。假设其是偶数，那么可以把$Q()$分解为$Q(x_1,…x_r)=2x_1R(x_2,…x_r)+S(x_2,…x_r)$。容易知道，当中$S()$仍然满足之前$P()$的要求，而$R(x_2,…x_r)$是一个次数为 1 的多项式
$$ \begin{aligned} \sum i^{Q(x_1,…x_r)}&=\sum i^{2x_1R+S}\\ &=\sum_{x_2,…x_r}i^S\sum_{x_1\in{0,1}}i^{2x_1R}\\ &=(1+(-1)^{R})\sum_{x_2,…x_r}i^S \end{aligned} $$
类似的，如果$x_1$的一次项系数是奇数，分解$Q(x_1,…x_r)=2x_1R(x_2,…x_r)+S(x_2,…x_r)+x_1$（注意所有的交错二次项的系数均是偶数，因此只有可能留下$x_1$单独的一次项）。此时有
$$ \sum i^{Q(x_1,…x_r)}=(1+(-1)^R\cdot i)\sum_{x_2,…x_r}i^S $$
考虑表达式之前的常数项，（不失一般性的）有
- $1+(-1)^R\cdot 1$
- $R=0\implies 2,R=1\implies 0$
- 可以用示性函数来表示，$2\mathcal{X}_{R=0}$
- $1+(-1)^R\cdot (-1)$
- $R=0\implies 0,R=1\implies 2$
- 可以用示性函数来表示，$2\mathcal{X}_{R=1}$
- $1+(-1)^R\cdot i$
- $R=0\implies (1+i),R=1\implies (1-i)$
- 注意到可以表示为$(1+i)\cdot (-i)^R$
- $1+(-1)^R\cdot (-i)$
- $R=0\implies (1-i),R=1\implies (1+i)$
- 注意到可以表示为$(1-i)\cdot (i)^R$
由于之前的分解$R(x_2,…x_r)$是一个次数为 1 的多项式
- 对于示性函数$\mathcal{X}_{R=0},\mathcal{X}_{R=1}$ ，可以在选出一个不自由的自变量 $x_i$ 由其他 $x_j$ 来表示，这样再次可以类似开始的消除不自由变量的递降
- 由于$S()$满足$P()$的条件，$R()$次数为 1，和二次项无关，因此$T(x_2,…x_r)=S()\pm R()$仍然满足$P()$的条件。此时$F$具有类似$\sum i^{T(x_2,…x_r)}$的形式，可以类似之前提出$x_1$的方法继续提出其他自变量
显然的这个过程（高斯消元解矩阵，多项式提取公共项等）可以在多项式时间内实现，$\mathcal{A}$确为一个易解类。
偶数条边的子图数目算法
有函数形式
$$ F=\left(\begin{matrix}1&1 \\ 1&-1\end{matrix}\right) $$
也可以认为是对于$x,y$，为$F(x,y)=i^{2xy}$。
对于图，点为$x_1,…x_n$，对每个边应用$F$。考虑取 1 的点构成的子图。子图有偶数条边，$-1$的偶数次幂为$+1$；奇数条边子图结果即为$-1$
因此问题结果为：偶数边子图数目-奇数边子图数目。已知 所有子图数目$2^{|V|}$=偶数边子图数目+奇数边子图数目。因此偶数边子图、奇数边子图数目计算为 $\mathcal{P}$ 问题
#CSP-第二易解类
集合$\mathcal{E}$有，$F\in\mathcal{E} \iff \exists \alpha\in \{0,1\}^n,\forall X\notin \{ \alpha,\bar{\alpha} \},F(X)=0$。这个集合可以认为是 n 元相等关系的推广。
注意到 $\{\alpha,\bar{\alpha}\}$是一个一维仿射子空间。一个自由变量相当于约束了其他非自由变量（对于求张量网络和来说）。
第二易解类$\mathcal{P}$，当函数为$\mathcal{E}$的乘积。注意到，连通的$\mathcal{E}$类型的函数，还是$\mathcal{E}$类型的函数。连通分支内部取值固定，连通分支之间取乘积即可（有结合律，易知）。
定义二元不等关系$\neq_2$为$[0,1,0]$。可以认为集合$\mathcal{E}$是由一个推广 n 元相等$[a,0..,0,b]$，取一些边接上二元不等关系$\neq_2$生成。这也是一种 构件替换规约。
图同态映射数目
图的同态映射，$\psi:V_G\to V_H$，有$\forall e=(a,b)\in E_G,(\psi(a),\psi(b))\in E_H$。给定一个图，求同态映射数目，相当于求一个二元函数$H$定义的$\#CSP$问题。
3 染色问题，可以认为是$H=\left(\begin{aligned}0,1,1\\1,0,1\\1,1,0\end{aligned}\right)$的$\#CSP(H)$问题
如果二元函数$H$对应的矩阵的秩小于等于 1，那么该问题为 $\mathcal{P}$问题。把分解二元函数$H=ab^{\prime}$。原来的图的每个顶点都相当于一个 n 元相等关系，只有两个赋值能满足，这样显然是易解的。
另一个易解类出现在如果图是二部图，有邻接矩阵$\begin{pmatrix} 0,A\\B,0 \end{pmatrix}$ ，当中的矩阵 A、B 秩都是 1。那么，如果另一图不是二部图，显然不存在同态映射；如果是二部图，考虑一部的顶点集合到另一个部的顶点集合，这时候化归到二元函数$H$对应的矩阵的秩小于等于 1 的情况。
斐波那契门
对于张量网络中的对称函数，如果$f_{i+2}=f_{i+1}+f_i$,那么$[f_0,f_1,f_2,…,f_k]$被称为斐波那契门。
斐波那契门的张量网络求值问题$\#\{Fib\}|\{=_2\}$，有多项式时间解法
算法一
对于$\#\{Fib\}|\{=_2\}$这样的张量网络，以下两种运算封闭
- 把两个斐波那契门函数用一条公共边$=_2$关系连在一起，形成一个新的斐波拉契门
- 考虑一个输入，一部分输入的 1 在一边，一部分在另一边，容易证明不管如何分配值不变
- 再证明这些输入的结果满足斐波那契关系
- 把一个斐波那契门函数的两条自由边成环在一起，新的函数还是新的斐波拉契门
- 容易证明$[f_0+f_2,f_1+f_3,…f_{k-2}+f_k]$这样的形式也是斐波那契门
因此对于上述网络重复上述两种操作，由于操作的封闭性和张量网络求值的结合律，最后可以得到一个超大的斐波那契门。表示，计算斐波那契门的输入输出都是多项式时间的。因此是$\mathcal{P}$问题。
算法二
考虑$x^2=x+1$，根为$a,b$，有韦达定理$ab=-1$。注意到$a^{i+2}=a^{i+1}+a^i$。那么$[1,a,a^2,…a^n]$满足$f_{i+2}=f_{i+1}+f_i$这样的递推关系。举个简单例子
$$ \begin{aligned} &(1,a)^{\otimes 3}\\ &=(1,a)\otimes (1,a,a,a^2)\\ &=(1,a,a,a^2,a,a^2,a^2,a^3)\\ &(000,001,010,011,100,101,110,111) \end{aligned} $$
因此，$(1,a)^{\otimes n},(1,b)^{\otimes n},s(1,a)^{\otimes n}+t(1,b)^{\otimes n}$都是斐波那契门。
反之，所有斐波那契门都能表示成$s(1,a)^{\otimes n}+t(1,b)^{\otimes n}$的形式。注意到
$$ \begin{pmatrix} f_{i+1}\\f_{i+2} \end{pmatrix}=\left(\Sigma\begin{pmatrix} a,0\\0,b \end{pmatrix}\Sigma^{-1}\right)^i\begin{pmatrix} f_{i}\\f_{i+1} \end{pmatrix}=\Sigma\begin{pmatrix} a,0\\0,b \end{pmatrix}^i\Sigma^{-1}\begin{pmatrix} f_{i}\\f_{i+1} \end{pmatrix}=T \begin{pmatrix} a^i\\b^i \end{pmatrix} $$
而且，定义$M=\begin{pmatrix} 1,a\\1,b \end{pmatrix}$，注意到
$$ \begin{aligned} &s(1,a)^{\otimes n}+t(1,b)^{\otimes n}\\ &=(s,0,…0,t)\begin{pmatrix} 1,a\\1,b \end{pmatrix}^{\otimes n}\\ &=[s,0,…0,t]\begin{pmatrix} 1,a\\1,b \end{pmatrix}^{\otimes n}=[s,0,…0,t]M^{\otimes n} \end{aligned} $$
使用全息规约，把斐波那契门的$M^{\otimes n}$项转移到二元相等关系上去。有
$$ \begin{aligned} &M^{\otimes 2}\begin{pmatrix} 1\\0\\0\\1 \end{pmatrix}\\ &=\begin{pmatrix} 1,a,a,a^2\\1,b,a,ab\\1,a,b,ab\\1,b,b,b^2 \end{pmatrix}\begin{pmatrix} 1\\0\\0\\1 \end{pmatrix}\\ &=\begin{pmatrix} 1+a^2\\0\\0\\1+b^2 \end{pmatrix} \end{aligned} $$
注意到，$[s,0,…0,t]$和$(1+a^2,0,0,1+b^2)$都属于集合$\mathcal{E}$。这时候可以调用 #CSP 第二易解类，product 形式的算法。因此可以多项式时间完成。
奇偶和相等关系转换
对于$H=\begin{pmatrix} 1,1\\1,-1 \end{pmatrix}$，有如下
$$ \begin{aligned} &[1,0,0,1]H^{\otimes 3}\\ &=((1,0)^{\otimes 3}+(0,1)^{\otimes 3})H^{\otimes 3}\\ &=(1,1)^{\otimes 3}+(1,-1)^{\otimes 3}\\ &=[1,1,1,1]+[1,-1,1,-1]\\ &=[2,0,2,0]=2[1,0,1,0] \end{aligned} $$
又有
$$ \begin{aligned} &[2,0,2,0]H^{\otimes 3}\\ &=((1,1)^{\otimes 3}+(1,-1)^{\otimes 3})H^{\otimes 3}\\ &=(2,0)^{\otimes 3}+(0,2)^{\otimes 3}\\ &=[2,0,0,0]+[0,0,0,2]\\ &=[2,0,0,2]=2[1,0,0,1] \end{aligned} $$
函数线性性质线性检测
对于$X,Y\in{0,1}^n$，对于一个线性函数$G:{0,1}^n\to{0,1}$.有$G(X+Y)\equiv G(X)+G(Y) \mod 2$。当中有形式$G=\sum a_ix_i,a_i\in{0,1}$
现在给出函数$G$，需要判断是否线性。则需要判断$G(X+Y)+G(X)+G(Y) \equiv0\mod 2$。如果不满足则不是线性函数。考虑变换$Z=X+Y$, 原有的判断条件可以改写为$(-1)^{G(X)}(-1)^{G(Y)}(-1)^{G(Z)}=1$。这时候，可以把 $(\text{通过概率}(1-p)-\text{拒绝概率}(p))$用张量网络求值表达出来。进行全息变换。$\oplus_3$替换为$=_3$ ,$(-1)^G$替换为$\hat{G}$
$$ \begin{aligned} 1-2p&=\sum\left((-1)^{G(X)}(-1)^{G(Y)}(-1)^{G(Z)}\prod \oplus_3(X_i,Y_i,Z_i)\right)\\ &=\sum \hat{G}(S)\hat{G}(U)\hat{G}(V)\prod =_3(S,U,V)\\ &=\sum \hat{G}^3(S) \\ &\le\sum (\max \hat{G}(S))\hat{G}^2(S)=\max \hat{G}(S) \end{aligned} $$
$\hat{G}$可以认为是$G$函数和对应选择的线性函数$\chi_s$的值相同的概率$1-\rho$减去值不同的概率$\rho$
注意到，bool 函数$G$和$\pm1$函数 $F:{1,-1}^n\to{1,-1}$之间是等价的，当中$F(X)=\prod_{j\in s}x_j$（注意这里把原先的$G$的 0 替换为$F$的 1，$G$的 1 替换为$F$的-1，$G$的奇数次的 1 有结果 1 对应$F$奇数次的-1 有结果-1）
考虑 Hadmard 的满秩矩阵，$H=\begin{pmatrix} 1,1\\ 1,-1 \end{pmatrix}$，$H^{\otimes n}$对应着关于不同的$x_j,j\in s$的$s$选取的真值表的基$\boldsymbol{\chi}_s,s\subseteq [n]$。以$n=2$为例
$$ \begin{aligned} H^{\otimes 2}=\begin{pmatrix} 1,1,1,1\\1,-1,1,-1\\1,1,-1,-1\\1,-1,-1,1 \end{pmatrix}\qquad\begin{matrix} 00\\01\\10\\11 \end{matrix} \end{aligned} $$
右边表示是否选取$x_0,x_1$。例如，$10$代表选择$x_0$，此时的线性函数为$\chi_{10}=x_0$。真值对应如下面的树状关系
| |
考虑一个 bool 函数按照上述转化而来的 $\pm 1$函数$F$的结果向量和某个$\chi_s$的内积$<F,\chi_s>$。由内积的定义，如果某位其相同，乘积为 1，反之为-1。那么内积的结果就是$F$和$\chi_s$之间相同点-不同点的数目。
这时候就可以定义相对距离$\rho$，不同的点数除以总点数。而值相同的概率减去值不同的概率一样表示为$1-2\rho$。因此，这是一个单边出错算法，拒绝概率$p\ge \rho$
容斥原理
$$ |\bigcap \bar{A}_i|=|S-\bigcup A_i|=|S|-\sum|A_i|+\sum|A_i\cap A_j|…+(-1)^n|A_1\cap…A_n| $$
定义$A_i(0)=\bar{A}_i,A_i(1)=A_i$，自变量$X\in{0,1}^n$，定义
$$ F(X)\triangleq |\bigcap A_i(x_i)| $$
定义 $A_i^*(0)=S,A_i^*(1)=A_i$ ，自变量 $X\in{0,1}^n$，定义
$$ H(X)\triangleq |\bigcap A_i^*(x_i)| $$
$$ \begin{aligned} H(01…1)= & |S\cap\bigcap_2 A_i^*(x_i)| \\ &=|A_1 \cap\bigcap_{2} A^{*}_{i}(x_i) |+|\bar{A}_1\cap\bigcap_2 A_i^{*}(x_i)| \\ &=F(01…1)+F(11…1) \\ &=(0,…0,1,0,…,0,1)\cdot\begin{pmatrix} F(0…0)\\ …\\ F(1…1) \end{pmatrix}\\ &=<(1,1)\otimes (0,1)^{\otimes n-1},\mathbf{F}> \end{aligned} $$
所以可以有（slide 上实际没有证明）
$$ \mathbf{H}=\begin{pmatrix} 1,1\\0,1 \end{pmatrix}^{\otimes n} \mathbf{F},\begin{pmatrix} 1,-1\\0,1 \end{pmatrix}^{\otimes n}\mathbf{H}=\mathbf{F} $$
那么就有，$F(0…0)=(1,-1)^{\otimes n}\mathbf{H}$。展开就能得到容斥原理的表达式。
Permanent
矩阵$A$的积和式，定义为
$$Permanent(M)=\sum_{\pi \in S_n}\prod M_{j,\pi(j)}$$
对于 $M$ ：
- n 个点带权有向图，所有圈的权重乘积之和；
- 二分图的所有完美匹配的权重乘积之和
- 这个定义对比行列式的定义，去除了符号项
Ryser 公式
可以定义矩阵的每行加起来，再乘积的结果$\phi(M)$
$$ \phi(M)=\prod(a_{11}+a_{12}+…)=\prod_i\sum_j a_{ij} $$
把$\phi(M)$展开，每一项对应每行出一个元素的连乘结果。定义坏事件$A_i$表示每行贡献一项的元素连乘结果，第$i$列没有贡献项。$\phi(M)$作为全集，而积和式可以用容斥原理表达为
$$ \begin{aligned} Perm(M)&=\sum\prod M_{i,\pi(i)}\\ &=\phi(M)-A_1-A_2…+A_1\cap A_2…\\ \end{aligned} $$
那么，有$k$个坏事件之交$\sum \bigcap^k A_i$结果为
$$T_k=\sum_{B是M的n\times(n-k)子式}\phi(B)$$
那么上述的容斥原理表达式，即可转成指数复杂度的 Ryser 公式，计算积和式
$$ \begin{aligned} Perm(M)&=\sum (-1)^kT_k\\ &=(-1)^n\sum_{S\subseteq\{1,…,n\}}(-1)^{|S|}\prod_i\sum_{j\in S}m_{ij} \end{aligned} $$
如果考虑积和式对应二分图的带权完美匹配的问题，那么有边的权重关系$(i,j^\prime)=(j^\prime,i)=A_{ij}$（当中$i,j^{\prime}$表示点出自不同部分）
对于二部图，每个点取对称函数$[0,1,0…0]$（1 个 1，n-1 个 0 时候输出 1，否则输出 0）。如果张量网络求值结果不为 1，说明每个顶点有且只有一条边取 1，那么此时取得完美匹配。。如果把张量网络里一部的点的函数换成$[0,1,1…1]=(1,1)^{\otimes n}-(1,0)^{\otimes n}=F_1+F_2$，值不变（n 次匹配，必须完美分配才能保证一边不出 0 值）。如果从里面选一个${(1,1)^{\otimes n},-(1,0)^{\otimes n}}$拆开来算，那么分别计算$2^n$次，但每一次当中，一边的点对应边要么全 0 要么全 1，相对简单好算。
模数意义下的快速算法
注意到积和式和行列式在模 2 意义下相等。而且积和式满足如下的关系
$$ Perm\begin{pmatrix} A_1+bB_1\\ A_2\\ …\\ A_n \end{pmatrix}=Perm\begin{pmatrix} A_1\\ A_2\\ …\\ A_n \end{pmatrix}+b\cdot Perm\begin{pmatrix} B_1\\ A_2\\ …\\ A_n \end{pmatrix} $$
因此可以提出在积和式 $\mod 2^k,k\in \mathbb{Z}^*$意义下的多项式时间算法。首先对于积和式进行高斯分解。假定对第二行有$A_2+kA_1=(0,*)$，那么就有$A_2=(-k)A_1+(0,*)$。利用上述积和式关系，一次分解，会将$n\times n$的方阵，分解出$n-1$个两行相等的积和式，加上一个$(n-1)\times(n-1)$更小的积和式。
令$T_k(n)$表示对$n\times n$的积和式计算$\mod 2^k$意义下的时间，$T_k^\prime(n)$表示对有两行相等的积和式计算$\mod 2^k$意义下的时间。有
$$T_k(n)=(n-1)\cdot T^\prime_k(n)+T_{k-1}(n)+O(n)$$
而对于两行相等的积和式，对两个相同行做展开，有，$T^\prime_k(n)\sim n^2T_{k-1}(n-2)$。因此有$T_k(n)<\Theta(n^{4k+3})$。
匹配问题
带权匹配问题规约
对于完美匹配问题，有如下规约关系。因此主要到#SAT 是#P 完全的，完美匹配计数问题也是#P 完全的
$$ \#SAT\le\#PerM_{\text{有权重}}\le\#PerM_{\text{0,1}} $$
第二个规约关系的证明。如果权重是正整数，$\star-k-\star$这样一条边可以替换为 $k-1$ 条$\star-0-1-0-\star$和一条$\star-1-\star$的边。因为如果该边在匹配中，顶点$\star$对外的其他边必取 0；而转换之后内部求和的完美匹配权重和的结果和只有一条权为$k$的边相同。
如果权重是任意的$w\in \mathbb{R}$。定义$X_i$为原图完美匹配中去除$i$条权重为$w$的边之后的部分权重和。那么全图权重和即为$\#G=\sum w^iX_i$。定义图$G_k$，是将原图的$i$条权重为$w$的边替换为上述$k$条边之后的结果。那么有$\#G_k=\sum k^iX_i$。计算图$G_k$的完美匹配数是计算 01 权重完美匹配数的问题，已经假定存在解法。那么，可以列出关系式
$$ \begin{pmatrix} …\\ \#G_k\\ \#G_l\\ … \end{pmatrix}=\begin{pmatrix} …\\ k^0,k^1,…k^n\\ l^0,l^1,…l^n\\ … \end{pmatrix}\begin{pmatrix} X_0\\ X_1\\ … \\ X_n \end{pmatrix} $$
注意到矩阵$\begin{pmatrix} …\\ k^0,k^1,…k^n\\ l^0,l^1,…l^n\\ … \end{pmatrix}$具有 Vandermonde 方阵的形式。Vandermonde 行列式是满秩的。因此可以直接求出$X_0,X_1,…X_n$，带回去就可以求解$\#G=\sum w^iX_i$。因此规约成立。
一般的匹配问题
一般的匹配问题的顶点的对称函数变成$[1,1,0…0]$。完美匹配问题可以规约到求解一般的匹配问题，证明如下
$$ \#PerfectMatch\le\#Match $$
考虑如下的一个张量网络，对其考虑匹配问题
| |
求值有，把其结果记为$F_k$。如果对应$*$的顶点取 0，结果即为$F_k(0)$，取 1 类似。
$$ \begin{aligned} &\begin{pmatrix} 1,1\\1,0 \end{pmatrix}^{k-1}\begin{pmatrix} 1\\1 \end{pmatrix}=\begin{pmatrix} 1,1\\1,0 \end{pmatrix}^{k}\begin{pmatrix} 1\\0 \end{pmatrix}\\ &=\frac{1}{\sqrt{5}}\begin{pmatrix} \frac{1+\sqrt{5}}{2},\frac{1-\sqrt{5}}{2}\\1,1 \end{pmatrix}\begin{pmatrix} (\frac{1+\sqrt{5}}{2})^k,0\\0,(\frac{1-\sqrt{5}}{2})^k \end{pmatrix}\begin{pmatrix} 1,\frac{\sqrt{5}-1}{2}\\ -1,\frac{\sqrt{5}+1}{2} \end{pmatrix}\begin{pmatrix} 1\\0 \end{pmatrix}\\ &=\frac{1}{\sqrt{5}}\begin{pmatrix} \frac{1+\sqrt{5}}{2},\frac{-1+\sqrt{5}}{2}\\1,-1 \end{pmatrix}\begin{pmatrix} \alpha^k\\ \beta^k \end{pmatrix} \end{aligned} $$
对于$n$个点的图$G$。定义$Y_i$,表示取一次图的匹配，留下$i$不参加匹配的完美匹配数目。显然，完美匹配数有$\#PM(G)=Y_0$，匹配数有$\#M(G)=\sum Y_i$。考虑修改图$G_k$，把原来图$G$的$n$点全都连接上之前的张量网络链。那么图$G_k$的匹配有（注意到，只有原先没有参与匹配的点，对于新加入的链可以取 1，参加和新的链之间的匹配，即出现$F_k(0)+F_k(1)$的组合）
$$ \begin{aligned} \#M(G_k)&=\sum Y_i(F_k(0)+F_k(1))^i(F_k(0))^{k-i}\\ &=F_k^n(0)\sum Y_i(\frac{F_k(0)+F_k(1)}{F_k(0)})^i\\ \end{aligned} $$
当中，有
$$ \begin{aligned} r_k=\frac{F_k(0)+F_k(1)}{F_k(0)}=\frac{\frac{3+\sqrt{5}}{2}\alpha^k+\frac{\sqrt{5}-3}{2}\beta^k}{\frac{1+\sqrt{5}}{2}\alpha^k+\frac{\sqrt{5}-1}{2}\beta^k}=\begin{pmatrix} a,b\\ c,d \end{pmatrix}\begin{pmatrix} \alpha^k \\ \beta^k \end{pmatrix} \end{aligned} $$
如果要求$s\neq t\implies r_s\neq r_t$，那么充要条件为$ad-bc\neq0,\frac{\alpha}{\beta}\neq 1$。容易验证这些条件都是满足的。由于假定已知求解图$G_k$的匹配的算法，类似上面的，$(r_k)^i$还是可以构造出 Vandermonde 方阵的形式。从而求解出$Y_0,Y_1,…Y_n$，从而得出完美匹配数$\#PM(G)=Y_0$。因为我们已知完美匹配是#P 完全问题，所以匹配问题也是#P 完全问题。
匹配门
用对称函数$[0,1,0…0]$和$[w_1,0,w_2]$构建的张量网络，称为匹配门$F:\{0,1\}^n\to \mathbb{C}$。假定两个输出$\alpha,\beta\in\{0,1\}^n$，把$\alpha,\beta$不相等的标号升序排列记为$\{p_1,p_2,…p_k\}$。那么，有匹配门等式
$$I(F,\alpha,\beta)=\sum (-1)^jF(\alpha\oplus p_j)F(\beta\oplus p_j)=0$$
由归纳法证明。起始函数是满足的。平面张量网络两个基本运算对匹配门等式封闭。（和斐波那契门算法 1 里的操作相似）
Juxtaposition
两个匹配门在平面上连在一起。（注意变量没有交错，平面条件在此）
$$F(x_1,..x_s,y_1,…y_t)=P(x_1,..x_s)Q(y_1,…y_t)$$
有
$$I(F,\alpha\alpha^\prime,\beta\beta^\prime)=Q(\alpha^\prime)Q(\beta^\prime)I(P,\alpha,\beta)\pm P(\alpha)P(\beta)I(Q,\alpha^\prime,\beta^\prime)=0$$
证毕
Jumper
匹配门两条边成自环，不妨设是$x_1,x_2$
$$F(x_3,…x_3)=P(0,0,x_3,…x_s)+P(1,1,x_3,…x_s)$$
有
$$ \begin{aligned} I(F,\alpha,\beta)&=I(P,00\alpha,00\beta)+I(P,11\alpha,11\beta)\\ &+(I(P,00\alpha,11\beta)+P(10\alpha)P(01\beta)-P(01\alpha)P(10\beta))\\ &+(I(P,11\alpha,00\beta)+P(01\alpha)P(10\beta)-P(10\alpha)P(01\beta))=0 \end{aligned} $$
证毕
附录-基础知识
Markov-Inequality
$$ \begin{aligned} &X\ge0,\forall c\ge0\\ &\implies Pr(X\ge c)\le\frac{E(X)}{c} \end{aligned} $$
证明是显然的
Chebyshev-Inequality
$$ \begin{aligned} &X,\forall c\ge 0\\ &\implies Pr(|X-E(x)|\ge c)\le\frac{Var(X)}{c^2} \end{aligned} $$
注意到$Pr(|X-E(x)|\ge c)=Pr((X-E(x))^2\ge c^2)$，然后化归到 Markov 不等式Chebyshev 不等式适用以下场景：
- 变量之间独立，方差等于各自方差和
- 变量之间负相关，可以放缩方差和
- 变量之间两两独立，但不独立（eg，2 个独立 01 变量，再一个为前两个的异或），协方差均为 0，方差等于各自方差和
抽样调查准确率
作为 Chebyshev 不等式的应用。 抽样 n 个，调查出来的概率$\hat{p}=\frac{X_1+…X_n}{n}=\frac{X}{n}$。对其和真实概率$p=\frac{|T|}{|U|}$的偏移有要求：
$$Pr(|\hat{p}-p|\le \Delta)\ge 1-\epsilon \implies Pr(|\hat{p}-p|\ge \Delta)\le \epsilon $$
$$ \begin{aligned} &Pr(|\hat{p}-p|\ge \Delta)\\ &=Pr(|\frac{X}{n}-p|\ge \Delta)\\ &=Pr(|X-np|\ge n\Delta)\\ &\le\frac{Var(X)}{(n\Delta)^2}\\ &\le\frac{1}{4n\Delta^2} \end{aligned} $$
要求的抽样$n$的取值只和要求的$\Delta,\epsilon$有关（$n\ge\frac{1}{4\epsilon\Delta^2}$），和真实概率$p$本身分布无关。但是，如果知道真实分布，可以改善$n$的取值。
如果使用 chernoff bound 去估计，可以指定相对误差$\delta\in(0,1)$。如果有如下的要求
$$Pr(\hat{p}\in[(1-\delta)p,(1+\delta)p])\ge 1-\epsilon$$
则有
$$ \begin{aligned} &Pr(|\hat{p}-p|\ge\delta )\\ &=Pr(|\frac{X_1+…X_n}{n}-p|\ge\delta)\\ &\le 2e^{-\frac{\delta^2}{3}n\mu} \end{aligned} $$
推出要求数目为$n\ge \frac{3(\ln 2-\ln\epsilon)}{\delta^2 p}$。改进为对错误率的对数形式。但是此时对$n$的要求和原始分布$p$有关。
组合数不等式
$$ (\frac{n}{m})^m\le\binom{n}{m}\le(\frac{ne}{m})^m $$
第一个小于等于证明：
$$ \begin{aligned} \binom{n}{m}&=\frac{n!}{m!(n-m)!}\\ &=\frac{(n)..(n-m+1)}{(m)…(1)}\\ &=\frac{n}{m}\frac{n-1}{m-1}…\frac{n-m+1}{1}\\ &\ge (\frac{n}{m})^m \end{aligned} $$
注意到$\frac{(\frac{n+2}{n+1})^n}{n+1}(n+2)=(1+\frac{1}{n+1})^{n+1}\le e$。进行数学归纳法，有$\frac{(n+1)^n}{n!}\le e^n$。第二个小于等于证明：
$$ \begin{aligned} \binom{n}{m}&=\frac{n!}{m!(n-m)!}\\ &=\frac{(n)…(n-m+1)}{m!}\\ &\le e^m\frac{(n)…(n-m+1)}{(m+1)^m}\\ &\le (\frac{ne}{m})^m \end{aligned} $$
Chernoff-Bound
$X_1,X_2,…X_n$为 n 个 01（如果不是，需要正规化 normalize ） 的独立随机变量，$Pr(X_i=1)=p_i$，考虑随机变量和$X=\sum X_i$，均值$E(X)=\mu=\sum p_i$。对于一个偏离$\forall \delta\in (0,1)$（正向偏差时候大于 1 也可以，主要是负向概率不能为负。而最后的 exp 形式放缩需要$\delta\in(0,1)$）。
$$ Pr(X\ge \mu(1+\delta))\le [\frac{e^\delta}{(1+\delta)^{1+\delta}}]^\mu\le e^{-\frac{\delta^2}{3}\mu} $$
$$ Pr(X\le \mu(1-\delta))\le [\frac{e^{-\delta}}{(1-\delta)^{1-\delta}}]^\mu\le e^{-\frac{\delta^2}{2}\mu} $$
放缩成双向的
$$ Pr(|X-\mu|\ge \delta\mu)\le 2e^{-\frac{\delta^2}{3}\mu} $$
eg：抛硬币 1000 次，800+次正面，$e^{-\frac{(3/5)^2}{3}\cdot \frac{n}{2}}$，指数小的概率，对比 Chebyshev 里面只能 1/n 级别
正向的证明
$$ \begin{aligned} &Pr(X\ge(1+\delta)\mu)\\ &=Pr(e^{\lambda X}\ge e^{\lambda(1+\delta)\mu})\qquad \lambda>0\\ &\le \frac{E(e^{\lambda X})}{e^{\lambda(1+\delta)\mu}}\\ &=\frac{\prod E(e^{\lambda X_i})}{e^{\lambda(1+\delta)\mu}}\\ &=\frac{\prod ((1-p_i)+p_ie^{\lambda})}{e^{\lambda(1+\delta)\mu}}\\ &=\frac{\prod (1+p_i(e^{\lambda}-1))}{e^{\lambda(1+\delta)\mu}}\\ &\le \frac{\prod e^{p_i(e^{\lambda}-1)}}{e^{\lambda(1+\delta)\mu}}\\ &=\frac{e^{(e^{\lambda}-1)\mu}}{e^{\lambda(1+\delta)\mu}}\\ &=e^{(e^\lambda-1-\lambda(1+\delta))\mu}\qquad \lambda=\ln(1+\delta)>0\\ &=e^{(1+\delta-1-(1+\delta)\ln (1+\delta))\mu}\\ &=[\frac{e^\delta}{(1+\delta)^{1+\delta}}]^\mu \end{aligned} $$
在 $\delta\in(0,1)$时候，可以改写$e^{(1+\delta-1-(1+\delta)\ln (1+\delta))\mu}$，得出上界估计$e^{-\frac{\delta^2}{3}\mu}$
$$ \begin{aligned} &\delta -(1+\delta)\ln (1+\delta)\\ &=\delta-(1+\delta)(\delta-\frac{\delta^2}{2}+\frac{\delta^3}{3}…)\\ &=(\frac{\delta^2}{2}-\frac{\delta^3}{3}…)-(\delta^2-\frac{\delta^3}{2}+\frac{\delta^3}{3}…)\\ &=-\frac{\delta^2}{2}+\frac{\delta^3}{6}…\\ &\le -\frac{\delta^2}{2}+\frac{\delta^2}{6}=-\frac{\delta^2}{3} \end{aligned} $$
负向的证明
类似的，
$$ \begin{aligned} &Pr(X\le(1-\delta)\mu)\\ &=Pr(e^{\lambda X}\ge e^{\lambda(1-\delta)\mu})\qquad \lambda<0\\ &\le \frac{E(e^{\lambda X})}{e^{\lambda(1-\delta)\mu}}\\ &=\frac{\prod E(e^{\lambda X_i})}{e^{\lambda(1-\delta)\mu}}\\ &=\frac{\prod ((1-p_i)+p_ie^{\lambda})}{e^{\lambda(1-\delta)\mu}}\\ &=\frac{\prod (1+p_i(e^{\lambda}-1))}{e^{\lambda(1-\delta)\mu}}\\ &\le \frac{\prod e^{p_i(e^{\lambda}-1)}}{e^{\lambda(1-\delta)\mu}}\\ &=\frac{e^{(e^{\lambda}-1)\mu}}{e^{\lambda(1-\delta)\mu}}\\ &=e^{(e^\lambda-1-\lambda(1-\delta))\mu}\qquad \lambda=\ln(1-\delta)<0\\ &=e^{(1-\delta-1-(1-\delta)\ln (1-\delta))\mu}\\ &=[\frac{e^{-\delta}}{(1-\delta)^{1-\delta}}]^\mu\\ \end{aligned} $$
在 $\delta\in(0,1)$时候，可以改写$e^{(1-\delta-1-(1-\delta)\ln (1-\delta))\mu}$，得出上界估计$e^{-\frac{\delta^2}{2}\mu}$
$$ \begin{aligned} &-\delta -(1-\delta)\ln (1-\delta)\\ &=-\delta+(1-\delta)(\delta+\frac{\delta^2}{2}+\frac{\delta^3}{3}…)\\ &=(\frac{\delta^2}{2}+\frac{\delta^3}{3}…)-(\delta^2+\frac{\delta^3}{2}+\frac{\delta^4}{3}…)\\ &\le -\frac{\delta^2}{2} \end{aligned} $$
Fermat-Little-Theorem
$$p\in prime\implies \forall a,a^p\equiv a\pmod p$$
$$(a,p)=1\implies a^{p-1}\equiv 1\pmod{p}$$
注意集合${1,2,…(p-1)}$和集合 ${1\times a,2\times a ,…(p-1)\times a}$在$\mod p$意义上相等。因此有
$(p-1)!\equiv a^{p-1}(p-1)!\pmod p\implies a^{p-1}\equiv 1\pmod{p}$
Carmichael-Number
是合数，但是能够保证通过 费马小定理的检测。
$N=561=3\times 11 \times 17,\forall a,(a,N)=1\implies a^{560}\equiv 1\pmod{561}$
可以使用 中国剩余定理证明 561 满足性质要求。
$$ \left\{ \begin{aligned} &a^{560}=(a^{2})^{280}=1^{280}\equiv 1\pmod{3}\\ &a^{560}=(a^{10})^{56}=1^{56}\equiv 1\pmod{11}\\ &a^{560}=(a^{16})^{35}=1^{35}\equiv 1\pmod{17} \end{aligned} \right. $$
有无数个 Carmichael Number，而且对于足够大的一个 m，$(m,2m)$之间一定有一个 Carmichael Number（论文证明）。
中国剩余定理
今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？
$$ \left\{ \begin{aligned} &x=2\pmod 3\\ &x=3\pmod 5\\ &x=2\pmod 7 \end{aligned} \right. $$
$$ \begin{aligned} x=2\times &70+3\times &21+2\times &15\\ (1,&0,0) &(0,1,0) (0,&0,1) \end{aligned} $$
可以认为是用不同的余数的基底组合而成。可以推广为以下同余方程组，保证有解
$$ \left\{ \begin{aligned} &x=n_1\pmod {m_1}\\ &x=n_2\pmod {m_2}\\ &…\\ &x=n_k\pmod {m_k} \end{aligned} \right. $$
解为
$$x\equiv \sum n_i\times M_i\pmod{\prod m_i}$$
当中
$$ \left\{ \begin{aligned} &M_i\equiv 0\pmod{\frac{\prod m_k}{m_i}}\\ &M_i\equiv 1\pmod{m_i} \end{aligned} \right. $$
有 Bezout 定理，$GCD(x,y)=1\iff \exists r,s,rx+sy=1$。因此可以表达为$M_i=r(\frac{\prod m_k}{m_i})=1-sm_i$。$r,s$通过辗转相除法的中间系数计算
Schwartz-Zippel-Lemma
对于数域$\mathbb{F}$，多项式$0\not\equiv P(y_1,…y_n)\in\mathbb{F}[y1,…y_n]$。独立随机在有限集$S$中取$r_1,…r_n\in S\subseteq \mathbb{F}$，有
$$ Pr(P(r1,…r_n)=0)\le\frac{\deg(p)}{|S|} $$
注意，对于多元多项式，每项的次数等于元的次数和，整个多项式的$\deg$为每项中的最大值。
数学归纳法证明，$n=1$时候，由代数基本定理容易知道,最多$\deg(P)$个根，不一定根全在$S$当中。假设$n=k$成立，对于$n=k+1$时候，分离出一个变元，如$y_1$，把$y_1$次数最高的项（设大小为 d）提出，
$$P(y1,…y_{k+1})=y_1^d\cdot Q(y_2,…y_{k+1})+R(y_1,…y_{k+1})$$
此时有$\deg(Q)\le \deg(P)-d,\deg(R)\le \deg(P)$
$$ \begin{aligned} &Pr(P(r_1,…r_{k+1})=0)\\ &=Pr(P=0,Q(r_1,…r_{k+1})=0)+Pr(P=0,Q\neq0)\\ &\le Pr(Q=0)+P(P=0,Q\neq 0)\\ &\le \frac{\deg(Q)}{|S|}+P(P=0,Q\neq 0)\\ &\le \frac{\deg(P)-d}{|S|}+P(P=0,Q\neq 0)\\ &\le \frac{\deg(P)-d}{|S|}+\frac{d}{|S|}\qquad\text{关于$y_1$的d次多项式的情况}\\ &=\frac{\deg(P)}{|S|} \end{aligned} $$