计算理论导论（cheat sheet）

pumping lemma：如果 \(A\) 是正则语言，那么存在一个整数 \(p\)，如果 \(s\in A\) 的长度 \(\ge p\)，那么 \(s\) 可以被切分成 3 段 \(s=xyz\) 满足：(1) \(xy^iz\in A\)；(2) \(|y|>0\)；(3) \(|xy|\le p\)。（证明：\(A\) 是正则语言，根据正则语言的定义说明存在 DFA 接受 \(A\)，设 \(p=|Q|+1\)，任意长度 \(\ge p\) 的必然走出了环，然后令 \(y\) 为最后一个经过的环形成的串）

pumping lemma for CFLs：如果 \(A\) 是 \(CFLs\)，那么存在一个整数 \(p\)，如果 \(s\in A\) 的长度 \(\ge p\)，那么 \(s\) 可以被切分成 5 段 \(s=uvxyz\)，满足：(1) \(uv^ixy^iz\in A\)；(2) \(|vy|>0\)；(3) \(|vxy|\le p\)。不妨设 \(CFG\) 是乔姆斯基范式，如果 \(s\) 足够长，必然有变元重复，去最后一个重复的变元，\(s\) 可以展开成一个树结构，其中 \(x\) 形成的串是 \(vxy\) 的子树，并且这两个是由同一个变元展开的，将 \(x\) 替换为 \(vxy\) 也是在 \(A\) 中的，因此 (1) 成立，(2) 显然成立，(3) 是因为是最后一个重复的变元。

\(\mathbf{P}=\bigcup_k\mathbf{DTIME}(n^k)\)，\(\mathbf{NP}=\bigcup_k\mathbf{NTIME}(n^k)\)，\(\mathbf{EXP}=\bigcup_k\mathbf{DTIME}(2^{n^k})\)，\(\mathbf{NEXP}=\bigcup_k\mathbf{NTIME}(2^{n^k})\)，\(\mathbf{PSPACE}=\bigcup_k\mathbf{SPACE(n^k)}\)，\(\mathbf{NPSPACE}=\bigcup_k\mathbf{NSPACE(n^k)}\)，\(\mathbf{L}=\mathbf{SPACE}(\log n)\)，\(\mathbf{NL}=\mathbf{NPSPACE}(\log n)\)。

Cook-Levin：\(\mathrm{SAT}\in\mathbf{NP}\)-\(\mathrm{complete}\)。对于 \(L\in \mathbf{NP}\)，设 1-tape 的散漫图灵机判定 \(L\)，将快照转移过程表示为 \(\mathrm{CNF}\)，以此说明 \(L\le_p \mathrm{SAT}\)。

\(\mathbf L\subseteq \mathbf{NL}=\mathbf{coNL}\subseteq\mathbf P\subseteq\mathbf{NP}\subseteq\mathbf{PSPACE}=\mathbf{NPSPACE}\subseteq\mathbf{EXP}\subseteq\mathbf{NEXP}\)。

\(\boldsymbol\Sigma_2^p:x\in L\Leftrightarrow \exists u\in\{0,1\}^{q(|x|)},\forall v\in \{0,1\},M(x,u,v)=1\)。同理可得 \(\boldsymbol\Pi_2^p\)。同理可得 \(\boldsymbol \Sigma_n^p\) 和 \(\boldsymbol\Pi_{n}^p\)。\(\boldsymbol\Sigma_k^p\subseteq\boldsymbol\Pi_{k+1}^{p}\subseteq\Sigma_{k+2}^p\)。\(\mathbf{PH}=\bigcup_k\boldsymbol\Sigma_k^p=\bigcup_k\boldsymbol\Pi_k^p\)。对任意 \(i\ge 1\)，如果 \(\boldsymbol\Sigma_k^p=\boldsymbol\Pi_k^k\)，则 \(\boldsymbol\Sigma_k^p=\mathbf{PH}\)。\(\mathbf{coNP}=\{L:\overline L\in\mathbf{NP}\}\)，\(\mathbf{coNP}:x\in L\Leftrightarrow\forall u\in\{0,1\}^{p(x)},M(x,u)=1\)。\(\mathbf{NL}=\mathbf{coNL}\)。\(\mathrm{PATH}\) 是 \(\mathbf{NL}\) 完全的。如果 \(\mathbf{P}=\mathbf{NP}\)，则 \(\mathbf{PH}=\mathbf{P}\)，\(\mathbf{BPP}=\mathbf P\)。

时间分层定理：\(f(n)\log f(n)=o(g(n))\)，则 \(\mathbf{DTIME}(f(n))\subset \mathbf{DTIME}(g(n))\)（证明：构造图灵机 \(M\)，用通用图灵机模拟 \(M_x\) 在 \(x\) 上 \(O(g(n)/\log n)\) 次，如果停机，返回相反的结果，没停机，返回 \(0\)。因此 \(M\) 是属于 \(\mathbf{DTIME}(g(n))\) 的，如果存在 \(M^\prime\in \mathbf{DTIME}(f(n))\) 模拟 \(M\)，那么 \(M^\prime(<M^\prime>)=M(<M^\prime>)\)，而 \(M^\prime\) 是 \(\mathbf{DTIME}(f(n))\) 的，因此会停机，因此会返回 \(1-M^\prime(<M^\prime>)\neq M(<M^\prime>)\)，矛盾）。非确定型时间分层定理：\(f(n+1)=o(g(n))\)，则 \(\mathbf{NTIME}(f(n))\subset\mathbf{NTIME}(g(n))\)（证明：惰性对角线方法，不会）。塞维奇定理：\(\mathbf{NPSPACE}(S(n))\subseteq \mathbf{SPACE}(S(n)^2)\)。空间分层定理：\(f(n)=o(g(n))\)，则 \(\mathbf{SPACE}(f(n))\subset \mathbf{SPACE}(g(n))\)。

对数空间规约：\(f:\{0,1\}^*\to\{0,1\}^*\) 称为隐式对数空间可计算的，若 \(f\) 是多项式有界的，并且语言 \(L_f=\{<x,i>|f(x)_i=1\}\) 和语言 \(L^\prime_f=\{<x,i>|i\le |f(x)|\}\) 均属于 \(\mathbf L\)。称语言 \(B\) 对数空间可规约到语言 \(C\)，记为 \(B\le_l C\)，如果存在隐式对数空间可计算函数 \(f\) 使得 \(x\in B\) 当且仅当 \(f(x)\in C\) 对任意 \(x\in\{0,1\}^*\) 成立。

量化布尔公式（\(\mathrm{QBF}\)）：形如 \(Q_1x_1Q_2x_2\dots\varphi(x_1,\dots,x_n)\) 的布尔公式。定义 \(\mathrm{TQBF}\) 是所有为真的量化布尔公式构成的语言，\(\mathrm{TQBF}\) 是 \(\mathbf{PSPACE}\) 完全的（证明：这里只证明 \(\forall L\in \mathbf{PSPACE},L\le_p\mathrm{TQBF}\)，令 \(M\) 是 \(S(n)\) 空间内判定 \(L\) 的图灵机且 \(x\in\{0,1\}^n\)，下面构造大小为 \(O(S(n)^2)\) 的 \(\mathrm{QBF}\) 使得它为真当且仅当 \(M\) 接受 \(x\)，令 \(m=O(S(n))\) 是编码 \(M\) 在长度为 \(n\) 的输入上的格局所需的二进制位的个数，存在布尔公式 \(\varphi_{M,x}\) 使得 \(\varphi_{M,x}(C,C^\prime)=1\Leftrightarrow C\) 和 \(C^\prime\) 是相邻格局，通过 \(\varphi_{M,x}\) 构造 \(\psi\) 使得大小多项式并且 \(\psi(C,C^\prime)=1\) 则存在 \(C\) 到 \(C^\prime\) 的有向路径，然后将 \(C_{start}\) 和 \(C_{accept}\) 带入 \(\psi\) 得到一个 \(\mathrm{QBF}\)，这个 \(\mathrm{QBF}\) 为真当且仅当 \(M\) 接受 \(x\)，接下来是计算 \(\psi\)，定义 \(\psi_i\) 表示是否存在长度不超过 \(2^i\) 的路径，有 \(\psi_i(C,C^\prime)=\exists C^{\prime\prime}\psi_{i-1}(C,C^{\prime\prime})\land\psi_{i-1}(C^{\prime\prime},C^\prime)\)，然而这个长度太长了，缩减公式规模，\(\psi_{i}(C,C^\prime)=\exists C^{\prime\prime}\forall D^1\forall D^2((D^1=C\land D^2=C^{\prime\prime})\lor (D^1=C^{\prime\prime}\land D^2=C^\prime))\Rightarrow \psi_{i-1}(D^1,D^2)\)，这样 \(\psi_m\) 的规模就是 \(O(m^2)\) 的）。\(\mathrm{QBF}\)-博弈（\(\mathbf{PSPACE}\) 完全问题）：\(\exists x_1\forall x_2\exists x_3\forall x_4\dots \forall x_{2n}\varphi(x_1,\dots,x_n)=1\)。

线路族和语言识别：\(T:\mathrm N\to \mathrm N\)，\(T(n)\) 规模的线路族是一系列布尔线路 \(\{C_n\}_{n\in \mathrm N}\)，其中 \(C_n\) 有 \(n\) 个输入位和一个输出位，并且其规模 \(|C_n|\le T(n)\) 对任意 \(n\) 成立。对于语言 \(L\)，如果存在 \(T(n)\) 规模的线路族 \(\{C_n\}_{n\in \mathrm N}\) 使得 \(x\in L\Leftrightarrow C_n(x)=1\) 对任意 \(x\in \{0,1\}^n\) 成立，则称 \(L\in \mathbf{SIZE}(T(n))\)。

\(\mathbf P_{/\mathbf{poly}}=\bigcup_k\mathbf{SIZE}(n^k)\)。\(\mathbf P\subset\mathbf P_{/\mathbf{poly}}\)（证明：每个运行时间为 \(O(T(n))\) 的图灵机 \(M\) 均可用运行时间为 \(O(T(n)^2)\) 的散漫图灵机 \(\tilde M\) 模拟（其带头移动独立于输入）。快照 \(z_i\) 由第 \(i\) 步时机器的状态和各个带头读取的符号组成，\(z_i\) 可以基于一些信息被计算出来，信息包括 \(x\)、前一步的快照 \(z_{i-1}\) 和快照 \(z_{i_1},\dots,z_{i_k}\)，其中 \(i_j\) 表示 \(M\) 的第 \(j\) 条带的带头在第 \(i_j\) 步时停留在第 \(i\) 步相同的位置上（由于是散漫图灵机，只与 \(i\) 有关）。这个线路是多项式规模，可在多项式时间求得，甚至可在对数空间内计算得到，因为 \(f(n,i)\) 表示将长度为 \(n\) 运行到第 \(i\) 步时带头所处的位置是对数空间可计算的）。所有一元语言均属于 \(\mathbf{P_{/\mathbf{poly}}}\)（包括部分不可判定问题，如停机问题的一元形式 ：\(\mathrm{UHALT}=\{1^n:\text{n是<M,x>二进制编码，M在输入x上停机}\}\)）。

一致线路：对于线路族 \(\{C_n\}\)，如果存在多项式时间的图灵机 \(M\) 在输入 \(1^n\) 上输出 \(C_n\) 的位串表示，则称线路族是 \(\{C_n \}\) 是 \(\mathbf P\) 一致的。如果将线路限定为 \(\mathbf{P}\) 一致线路，则类 \(\mathbf{P_{/\mathbf{poly}}}\) 坍塌到类 \(\mathbf{P}\)。

非一致分层定理：对于任意满足满足 \(2^n/n>T^\prime(n)>10T(n)>n\) 的两个函数，均有 \(\mathbf{SIZE}(T(n))\subset \mathbf{SIZE}(T^\prime(n))\)（证明：对于任意 \(\ell\)，存在函数 \(f:\{0,1\}^\ell\to\{0,1\}\) 不能被规模 \(2^{\ell}/(10\ell)\) 的线路计算，但均可被规模 \(\frac{2^\ell}\ell(1+o(1))\) 的线路计算）。

类 \(\mathbf{NC}\) 和类 \(\mathbf{AC}\)：对于任意 \(d\)，如果存在判定语言 \(L\) 的线路族 \(\{C_n\}\)，使得 \(C_n\) 的规模为 \(\mathrm{poly}(n)\) 且深度为 \(O(\log^dn)\)，则称 \(L\) 属于类 \(\mathbf{NC}^d\)。类 \(\mathbf{NC}=\bigcup_{i\ge 1}\mathbf{NC}^i\)。类 \(\mathbf{AC}^i\) 的定义与类 \(\mathbf{NC}^i\) 的定义类似，不过或门和与门可以作用到多于两个的位上。\(\mathbf{AC}=\bigcup_{i\ge 1}\mathbf{AC}^i\)。\(\mathbf{NC}^i\subseteq \mathbf{AC}^i\subseteq \mathbf{NC}^{i+1}\)。\(\mathrm{PARITY}=\{x:x\text{含有奇数个1}\}\not \in \mathbf{AC}^0\)。\(\mathbf{NC}^1\subseteq\mathbf L\subseteq\mathbf{NL}\subseteq\mathbf {AC}^1\)（第三个属于的证明：对于输入 \(x\)，格局图是多项式的，写成矩阵，矩阵乘法是 \(\mathbf{AC}^0\) 的，快速幂是 \(\mathbf{AC}^1\) 的）。

对数空间一致线路：对于线路族 \(\{C_n\}\)，如果存在隐式对数空间可计算函数将 \(1^n\) 映射为线路 \(C_n\) 的位串表示，则称线路族 \(\{C_n\}\) 是对数空间一致的。对数空间一致当且仅当如下函数是 \(O(\log n)\) 空间可计算的：\(\mathrm {SIZE}(n)\) 返回线路规模；\(\mathrm{TYPE}(n,i)\) 返回第 \(i\) 个点的标记（与，或，非，不存在）；\(\mathrm{EDGE}(n,i,j)\) 输出 \(1\) 表示线路 \(C_n\) 中 \(i\) 到 \(j\) 有一条有向边。语言 \(L\) 存在多项式规模的对数空间一致线路 \(\Leftrightarrow L\in \mathbf P\)（证明："\(\Rightarrow\)"：线路可以在多项式时间生成并模拟；"\(\Leftarrow\)"：见 $\mathbf P\subseteq \mathbf P_{/\mathbf{poly}} $ 的证明，线路是对数空间可计算的）。

纳言图灵机：在每个 \(n\) 值上有个建言 \(\alpha_n\)，可以在输入长度为 \(n\) 的任意输入上计算时使用。\(\mathbf{P_{/\mathbf{poly}}}=\bigcup_{c,d}\mathbf{DTIME}(n^c)/n^d\)。

概率型图灵机：\(M\) 在 \(T(|x|)\) 时间停机且 \(\Pr[M(x)=L(x)]\ge \frac 23\)。\(\mathbf{BPTIME}(T(n))\) 是概率型图灵机在 \(O(T(n))\) 时间内判定的所有语言构成的类，并定义 \(\mathbf{BPP}=\bigcup_k\mathbf{BPTIME}(n^k)\)。另一种定义：\(\Pr_{r\in \mathrm R^{\{0,1\}^{p(|x|)}}}[M(x,r)=L(x)]\ge \frac 23\) 对任意 \(x\in\{0,1\}^*\) 成立。根据定义易知 \(\mathbf P\subseteq\mathbf{BPP}\subseteq \mathbf{EXP}\)。\(\mathbf{BPP}\overset{如果\mathbf P=\mathbf{NP}}=\mathbf P\)。\(\mathbf{BPP}\subseteq \mathbf{P_{/\mathbf{poly}}}\)（证明：每个 \(n\) 可以钦定随机串给 \(C_n\)，使得没有错误率），\(\mathbf{BPP}\subseteq \boldsymbol\Sigma_2^p\cap \boldsymbol\Pi_2^p\)。\(\mathbf{RTIME}(T(n))\) 包含所有语言 \(L\)，能被一个运行时间为 \(T(n)\) 的概率型图灵机 \(M\) 识别，并且 \(x\in L\Rightarrow\Pr[M(x)=1]\ge \frac 23\)，\(x\not \in L\Rightarrow \Pr[M(x)=0]=1\)。定义 \(\mathbf{RP}=\bigcup_k \mathbf{RTIME}(n^k)\)。\(\mathbf{ZTIME}(T(n))\) 包含所有语言，它能被一个运行时间的期望为 \(T(n)\) 的概率型图灵机 \(M\) 识别，且 \(M\) 的输出总是正确的。定义 \(\mathbf{ZPP}=\bigcup_k\mathbf{ZTIME}(n^k)\)。有结论 \(\mathbf{ZPP}=\mathbf{RP}\cap\mathbf{coRP}\)。同理可以定义出 \(\mathbf{BPL}\) 和 \(\mathbf{RL}\)（\(M\) 为 \(O(\log n)\) 空间的概率型图灵机）。\(\mathrm{UPATH}\in \mathbf{RL}\)（无向图连通性判定问题）。注意到 \(\mathbf{RL}\subseteq \mathbf{NL}\)，进而 \(\mathbf{RL}\subseteq \mathbf P\)。还有结论 \(\mathbf{BPL}\subseteq \mathbf P\)（作业题，设 TM \(M\) decides \(L\in\mathbf{BPL}\)，对于一个输入 \(M\) 的格局图是多项式的，矩阵幂算出起点到接收状态的概率）。定义 \(\mathbf{BP}\cdot\mathbf{NP}=\{L:L\le_r \mathrm{3SAT}\}\)。\(\mathbf{BP}\cdot\mathbf{NP}\subseteq \mathbf{NP}_{/\mathbf{poly}}\)（作业题，\(\Pr[L(x)=\mathrm{3SAT(M(x,r))}]\ge \frac 23\)，这个 \(\frac 23\) 经过多次试验可以取到 \(2^{-n-1}\)，因此每个 \(x\) 最多有 \(\frac{2^m}{2^{n+1}}\) 个错误的种子，因此存在种子每个都正确，即存在线路每个都正确，将 \(C_n\) 作为 \(\mathrm{advice}\) 即可 ）。

随机规约：如果存在多项式时间概率型图灵机使得 \(\Pr_r[B(x)=C(M(x,r))]\ge \frac 23\) 对任意 \(x\in\{0,1\}^*\) 成立，则 \(B\le_rC\)。

确定型函数的交互：设 \(f,g:\{0,1\}^*\to \{0,1\}^*\) 是两个函数，\(k\) 是一个整数（取值可以依赖输入规模），定义 \(a_1=f(x),a_2=g(x,a_1),\dots,a_{2i+1}=f(x,a_1,\dots,a_{2i}),a_{2i+2}=g(x,a_1,\dots,a_{2i+1})\)，交互结束时 \(f\) 的输出定义为 \(f(x,a_1,\dots,a_k)\)，记为 \(\mathrm{out}_f<f,g>(x)\in\{0,1\}\)。称语言 \(L\) 存在确定型交互证明系统，如果存在确定型图灵机 \(V\) 在输入 \(x,a_1,\dots,a_i\) 上运行时间是 \(|x|\) 的多项式，且 \(V\) 可以与任意函数 \(P\) 交互 \(k\) 个回合，使得：\(x\in L\Rightarrow\exists P:\{0,1\}^*\to\{0,1\}^*\) 满足 \(\mathrm{out}<f,g>(x)=1\)，\(x\not\in L\Rightarrow\forall P:\{0,1\}^*\to\{0,1\}^*\) 满足 \(\mathrm{out}<f,g>(x)=0\)。类 \(\mathbf{dIP}\) 包含所有存在 \(k(n)=\mathrm{poly(n)}\) 回合确定型交互证明系统的语言。事实上，\(\mathbf{dIP}=\mathbf{NP}\)（证明：显然任意 \(\mathbf{NP}\) 的语言存在1-回合确定型证明系统，现在证明 \(L\in \mathbf{dIP}\Rightarrow L\in \mathbf{NP}\)，设 \(V\) 是 \(L\in\mathbf{dIP}\) 的验证者，说明对于输入 \(x\) 存在使 \(V\) 接受的笔录 \((a_1,\dots,a_k)\)，只需查验 \(V(x)=a_1,V(x,a_1,a_2)=a_3\dots V(x,a_1,\dots,a_k)=1\) 确实成立，这是 \(\mathbf{NP}\) 的。反过来，如果上述笔录存在，则证明者函数 \(P\) 可以定义（因为传入了 \(x\)））。

概率型验证者和类 \(\mathbf{IP}\)：对于整数 \(k\ge 1\)（\(k\) 可以依赖于输入的长度），称语言 \(L\) 属于 \(\mathbf{IP}[k]\)，如果存在一个概率型多形式时间图灵机 \(V\)，它可以与任意函数 \(P:\{0,1\}^*\to\{0,1\}^*\) 进行 \(k\) 个回合的交互使得：\(x\in L\Rightarrow\exists P,\Pr[\mathrm{out}<V,P>(x)=1]\ge \frac 23,x\not \in L\Rightarrow \forall P,\Pr[\mathrm{out}<V,P>(x)=1]\le \frac 13\)。定义 \(\mathbf{IP}=\bigcup_{k\ge 1} \mathbf{IP}[n^k]\)。\(\mathbf{IP}=\mathbf{PSPACE}\)（只需证明 \(\mathbf{PSPACE}\subseteq \mathbf{IP}\)，转为证明 \(\mathrm{TQBF}\in\mathbf{IP}[\mathrm{poly}(n)]\)，证明在后面）。证明 \(\overline{\mathrm{3SAT}}\in \mathbf{IP}\)（转为证明 \(\#\mathrm{SAT}_D=\{<\phi,K>:\phi\text{是一个3CNF公式并且恰存在K个满足性赋值}\}\in\mathbf{IP}\)，证明者取质数 \(p\in (2^n,2^{2n}]\)，验证者验证 \(p\) 是质数（这里可以是概率型素性测试算法），然后用下面的方法校验）

给定 \(d\) 次多项式 \(g(X_1,\dots,X_n)\)，整数 \(K\) 和一个素数 \(p\)，我们说明证明者如何通过交互式协议向验证者证明论断 \(K=\sum_{b_1\in\{0,1\}}\sum_{b_2\in\{0,1\}}\dots\sum_{b_n\in\{0,1\}}g(b_1,\dots,b_n)\)，所有计算都在 \(\bmod p\) 意义进行，并且 \(g\) 具有多项式规模的表示形式，这样验证者就能算 \(g(b_1,\dots,b_n)\)。和校验协议：\(V\)：如果 \(n=1\)，验证 \(g(0)+g(1)=K\) 是否成立。如果是，则接受，否则拒绝；如果 \(n\ge2\)，则要求证明者 \(P\) 发送 \(h(X_1)=\sum_{b_2\in\{0,1\}}\dots\sum_{b_n\in\{0,1\}}g(X_1,b_1,\dots,b_n)\)。\(P\)：向验证者发送多项式 \(s(X_1)\)，如果证明者没有“欺骗"验证者，则有 \(s(X_1)=h(X_1)\)。\(V\)：如果 \(s(0)+s(1)\neq K\) 则拒绝，否则从 \(\mathrm F_p\) 中选择一个随机数 \(a\)，递归地利用本协议验证 \(s(a)=\sum_{b_2\in\{0,1\}}\dots\sum_{b_n\in\{0,1\}}g(a,b_2,\dots,b_n)\)。

对于 \(\mathrm{TQBF}\)，\(\Psi\in\mathrm{TQBF}\Leftrightarrow \prod_{b_1\in\{0,1\}}\sum_{b_2\in\{0,1\}}\dots\sum_{b_n\in\{0,1\}}P_\phi(b_1,\dots,b_n)\neq 0\)。用和校验协议的方法多项式 \(h(X_1)\) 的次数太大，注意到 \(x^k=x,\forall x\in\{0,1\}\)，因此可以将 \(X_i\) 的次数变成一次，设这个操作为 \(L_{X_i}\)，变成如下表达式 \(\forall X_1L_1\exists X_2L_1L_2\dots\exists X_nL_1L_2\dots L_nP_\phi(X_1,\dots,X_n)\)，这样关于 \(h(X_1)\) 的次数就低了。（细节：设 \(U(X_1,\dots,X_1)=\mathcal O\ g(X_1,\dots,X_k)\)，\(l=k\) 或 \(k-1\)（取决于 \(\mathcal O\)）。\(\mathcal O=\exists X_1\)，证明者将一个 \(d\) 次多项式 \(s(X_1)\) 当作 \(g(X_1,a_2,\dots,a_k)\) 发送给验证者。验证者检验 \(s(0)+s(1)=C^\prime\) 是否成立。不成立拒绝，否则随机选取 \(a\in \mathrm F_p\) 并要求证明者证明 \(s(a)=g(a,a_2,\dots,a_k)\)。\(\mathcal O=\forall X_1\)，前面相同，检验 \(s(0)s(1)=C'\)。\(\mathcal O=L_{X_1}\)，证明者希望向验证者证明 \(U(a_1\dots,a_n)=C'\)。证明者将 \(d\) 次多项式 \(s(X_1)\) 当作 \(g(X_1,a_2,\dots,a_n)\)，验证者验证 \(a_1s(0)+(1-a_1)s(1)=C'\) 是否成立，不成立拒绝，否则随机 \(a\in\mathrm F_p\)，要求证明者证明 \(s(a)=g(a,a_2,\dots,a_k)\)。）

\(\mathbf{AM}[k]\) 定义为验证者只能发送随机比特 \(\mathbf{IP}[k]\)，且不能用使用其它的随机比特。结论：\(\mathbf{AM}[2]=\mathbf{BP}\cdot \mathbf{NP}\)，\(k\ge 2\) 时，\(\mathbf{AM}[k]=\mathbf{AM}[2]\)。事实上，\(\mathbf{IP}[k]\subseteq \mathbf{AM}[k+2]\)。\(\mathrm{GNI}\in\mathbf{AM}[2]\)。

Hoeffding's Inequality：独立的随机变量 \(X_1,\dots,X_n\)，\(X_i\in[a_i,b_i]\)，令 \(X=\sum_{i=1}^n X_i\)，\(\mu=\mathbb E(X)\)，则 \(\Pr[X\le \mu-\lambda]\le \exp(\frac{-2\lambda^2}{\sum_{i=1}^n(b_i-a_i)^2})\)，\(\Pr[X\ge \mu+\lambda]\) 同理。