Regular Languages

略

DFA

略.

NFA

考虑一个五元组$Q,\Sigma,\delta,q_{start},F$,比起DFA,这里的$\delta:Q\times \Sigma_{\epsilon}\to 2^Q$,也即现在一个点可能会有若干条字符相同的边指向若干其它结点.

利用NFA容易证明当$A,B$是正则语言的时候,$A\circ B,A^*,A\cup B$都是正则语言.

GNFA

考虑一个五元组$Q,\Sigma,\delta,q_{start},F$,这里其实一般认为$F=\{q_{end}\}$.比起NFA,其$\delta$变为了一个函数$(Q-F)\times (Q-\{q_{start}\})\to R$,其中$R$是正则表达式的集合,也就是每条边匹配的从一个字符变成了一个正则表达式.下面我们要证明所有的单接收状态GNFA都可以由RE表示.

证明比较平凡,直接考虑每次删掉一个点,然后把其它的所有点两两配对考虑经过这个点的情况,把相应的边concat起来.然后如果有自环就加$*$,如果有重边就加$|$,这样就搞定了.

显然DFA可以转为一个GNFA(接收状态稍微收集一下),这也证明了RE的表达能力不弱于DFA.

Pumping Lemma

如果$A$是一个正则语言,那么$\exists p\in \mathbb{N}$,使得只要$s\in A\land |s|\geq p$,那么存在一种切分$s=xyz$使得:

  1. $\forall i\geq 0,xy^iz\in A$.
  2. $|y|>0$.
  3. $|xy|\leq p$.

也就是足够长的串总会在不任意靠后的地方出现非平凡循环体.

证明办法的话,考虑先转为DFA,这个DFA总共就这么几个结点,不妨直接设$p=|Q|$,那么超过$p$后,考虑经过的状态点序列共有$|Q|+1$个,显然总会有重复的结点,也就是在它们中走了一个环,重复这个环即可.

我依稀记得我在coq中用induction技巧不途径DFA证明过这个,但我忘了咋搞的了x.

Context-Free Languages

考虑一个四元组$(V,\Sigma,R,s)$,其中:

  1. $V$是variables.
  2. $\Sigma$是terminals
  3. $R$是rules
  4. $s\in V$是start variable

PDA

考虑一个五元组$(Q,\Sigma,\Gamma,\delta,q_{start},F)$,比起NFA,它多了一个$\Gamma$表示堆栈的字母表.此时$\delta:Q\times \Sigma_\epsilon\times \Gamma_\epsilon\to \mathcal{P}(Q\times \Gamma_\epsilon)$.

转移现在成为了两串$s_0,\cdots,s_m$和$t_0,\cdots, t_m$,满足:

  1. $s_0=q_{start},t_0=\epsilon$.
  2. 当$t_i=ar,t_{i+1}=br$时,需要有$(s_{i+1},b)\in \delta(s_i,w_{i+1},a)$.
  3. $s_m\in F$.

现在我们来证明CFL和PDA等价.

先看如何证明能被CFL生成的都能被PDA识别.问题显然仅仅在于我不知道我当前在匹配哪条规则,所以我们直接把这个压入栈中就行了.后面匹配完成后再逐渐把后半部分的字符消灭掉,毛估估一下.

再看怎么证明PDA能识别的都能被CFL生成.我们先改造这个PDA满足:

  1. 只有一个接收节点.
  2. 接受的时候必须清空堆栈.
  3. 每次转移要么进行压入,要么进行弹出.

显然这些都可以做一些平凡的转化得到.

定义$A_{pq}$为:一个空栈从$p$出发,到$q$的时候栈仍然是空的情况.现在我们把以下两种规则加入:

  1. 对于状态$p,r,s,q$,如果遇到$a$字符,$p\to r$会压入$u$;遇到$b$字符,$s\to q$会弹出$u$.则将$A_{pq}\to aA_{rs}b$.
  2. 对于状态$p,r,q$,直接添加规则$A_{pq}\to A_{pr}A_{rq}$.
  3. 对于状态$p$,直接添加规则$A_{pp}\to \epsilon$.

其实还是在做括号序列.我们来看为何能被PDA识别的都能被CFL生成.原因是如果能被PDA识别,去看它的括号序列,就可以反映出上面的这些部分.

Pumping Lemma

如果$A$是一个CFL,则$\exists p\in \mathbb{N}$,使得$\forall s\in A$且$|s|\geq p$,那么可以划分$s=uvxyz$使得:

  1. $\forall i\geq 0,uv^ixy^iz\in A$.
  2. $|vy|>0$.
  3. $|vxy|\leq p$.

接下来我们考虑最简的一种推理方式,即运用最少次规则推导出来.

由于$|V|,|\Sigma|,|R|$都是有限的,我们考虑设$b=\max_{r\in R}(\#\{\text{symbols in RHS of r}\})$,这里的symbols指的是Terminals或Variables.此时,一个高度为$h$的推理串,得到的长度最多是$b^h$.如果$h>|V|$,那么就至少存在一条推理串上,同一个Variable出现了两次.因此如果一个串的长度超过了$b^{|V|+1}$,则它的高度$h>|V|$,因此可以找到一个Variable最终递归调用回了自己.取$p=b^{|V|+1}$,我们假设这个做到了$B\to s_1Bs_2\to s_1s_3s_2$.容易把这个东西替换上去或者替换下去,这样就证明了(1).

现在来看(2),如果$|vy|=0$,这意味着我们做了一圈$B\to B$,这显然不是最简的推理方式.

最后来看(3),只需要找最靠下的$|V|+1$层,然后去做上面的过程就行.

Turing Machine

一个$k$-tape的图灵机是一个七元组$(Q,\Sigma,\Gamma,\delta,q_0,q_{accept},q_{reject})$.其中:

  1. $Q$作为状态集.
  2. $\Sigma$作为输入字符表.
  3. $\Gamma$作为tape字符表.
  4. $\delta:Q\times \Gamma^k\to Q\times \Gamma^k\times \{L,S,R\}^k$

一般而言,输入的字符在第一个纸带上.

我们说一个图灵机接受一个$w$,当且仅当存在一列configuration $C_0,\cdots,C_t$,使得上述转移.

我们称一个语言是Turing-recognizable的,当且仅当存在一个图灵机接受它(可以不停机或者拒绝).我们称一个图灵机是decidable的,当且仅当它永远不会陷入死循环,一定会到达一个Halt状态.

现在我们想要探索这些东西的边界:

  1. 是否存在一个语言不可被recognized.
  2. 是否存在一个语言可以被recognized,但是不可被decided.

对于(1)是一个很自然的事.图灵机的数量是可数的,但是语言的集合显然是不可数的.这就完蛋了.

称一个语言$A$对于$B$是mapping reducible的(记作$A\leq_m B$).如果存在一个decidable的函数$f:\Sigma_A^*\to \Sigma_B^*$,使得$\forall w,w\in A\Leftrightarrow f(w)\in B$.有如下性质:

  1. 如果$B$是decidable的,那么$A$一定是decidable的.
  2. 如果$A$是undecidable的,那么$B$一定是undecidable的.
  3. $A\leq_m B$当且仅当$\bar{A}\leq_m \bar{B}$.

来看:

  1. $UC=\{\alpha|M_\alpha(\alpha) \text{unaccept}\}$.
  2. $EQ_{TM}=\{(M_1,M_2)|L(M_1)=L(M_2)\}$.
  3. $E_{TM}=\{M|L(M)=\emptyset\}$.
  4. $HALT=\{(M,\alpha)|M(\alpha)\text{halt}\}$
  5. $A_{TM}=\{(M,\alpha)|M(\alpha)\text{accept}\}$

我们可以证明:

  1. $E_{TM}\leq_m EQ_{TM}$.
  2. $A_{TM}\leq_m \overline{E_{TM}}$.
  3. $A_{TM}\leq_m EQ_{TM}$.
  4. $UC,EQ_{TM},E_{TM},A_{TM},HALT$都是undecidable的.
  5. $\overline{UC},\overline{E_{TM}},A_{TM},HALT$都是recognizable的.

现在需要搞定$\overline{A_{TM}}$是unrecognizable的.

引理: 一个语言$A$是decidable的,当且仅当$A$和$\bar A$都是recognizable的.

这条引理可以证明$UC,E_{TM},\overline{A_{TM}},\overline{HALT}$都是unrecognizable的.现在来看如何证明$EQ_{TM}$和$\overline{EQ_{TM}}$都是unrecognizable的.

而$\overline{A_{TM}}\leq_m E_{TM}\leq EQ_{TM}$,这就证明了$EQ_{TM}$是unrecognizable的.

而显然$A_{TM}\leq_m EQ_{TM}$,同时取补得到$\overline{EQ_{TM}}$是unrecognizable.

Time Complexity

设$\mathrm{DTIME}(T(n))$为一个包含那些能在$O(T(n))$时间内解决的语言的集合.设$P$为$\bigcup_{c\geq 0}\mathrm{DTIME}(n^c)$,以及$EXP$为$\bigcup_{c\geq 0}\mathrm{DTIME}(2^{n^c})$.

定义$NP$为存在一个多项式时间的函数$P$以及一台多项式时间的验证机器$M$,使得对于每个$x$,要判断其$x\in L$,当且仅当存在一个$u\in \{0,1\}^{P(|x|)}$使得$M(x,u)=1$.

另一种定义NP的方式是用NDTM来定义,定义NP为所有可以被NDTM在多项式时间内判定的问题的集合.

下面我们来证明这两种定义等价.不妨设它们分别是NP1和NP2.

先证明$NP1\subseteq NP2$.说明$L\in NP1\Rightarrow L\in NP2$.这个方式看上去就比较简单,直接让NDTM跑的时候去猜$u$的每一位是什么就行.

对于$NP2\subseteq NP1$,只需要记录下来每一步走得什么选择,用这个反过来就可以得到一个确定性的图灵机.

Time Hierarchy Theorem

如果$f$和$g$满足$f\log f=o(g)$,则$\mathrm{DTIME}(f(n))\subsetneq \mathrm{DTIME}(g(n))$.

包含关系是显然的.问题在于找一个语言在$\mathrm{DTIME}(g(n))$中而不在$\mathrm{DTIME}(f(n))$中.

现在考虑一个$L$,对于一个输入$x$,如果$M_x(x)$在$g(|x|)$步内停机,那么$L$输出$M_x(x)$的取反;否则输出reject.显然$L\in \mathrm{DTIME}(g(n))$,现在来看假设$L\in \mathrm{DTIME}(f(n))$,则存在一台图灵机$M_z$能判定该问题,那至少其输入$z$后能在$O(f(|z|))$内输出$M_z(z)=L(z)$.可是通用图灵机模拟$M_z(z)$只需要$O(f(|z|)\log f(|z|))$,因此$L(z)$一定会是$M_z(z)$的取反.这就矛盾了.

P-NP

定义多项式时间归约当且仅当存在一个多项式时间计算的$f_p:A\to B$,使得$a\in A$当且仅当$f(a)\in B$.此时我们说$A\leq_p B$,能解决$B$就能解决$A$.

定义一个语言$L$,是NP-hard的,当且仅当$\forall A\in NP$,$A\leq_p L$.

定义一个语言$L$是NP-complete,当$L$是NP-hard而且$L$也是$NP$.

Cook-Levin Theorem

考虑一个Bool表达式(只包含原子变量和与或非),定义一个$\varphi$是CNF的当且仅当它始若干个OR连接的东西AND起来.大概长成$\land_i(\lor_j v_{i,j})$,其中$v_{i,j}$要么是一个变量,要么是一个变量取反.如果后面的$\lor_j v_{i,j}$的项数都不超过$k$,则称其为$k$-CNF.定义SAT是所有可满足的CNF公式,定义3-SAT是所有可满足的3-CNF公式.

下面我们证明SAT和3-SAT都是NPC.

显然SAT和3-SAT都是NP的(只要给一组赋值就行).下面我们来证明对于任意$L\in NP$,都总有$L\leq_p SAT$.

我们想要搞一个多项式时间可计算的函数$f:x\to \psi_x$,使得$x\in L$当且仅当$\psi_x$可满足.

考虑转化为对configuration序列进行判断,考虑搞一个$T(n)\times T(n)$大小的二维表格,第$k$行表示在第$k$时刻,纸带上的情况.所有的转移规则都可以用Bool表达式刻画.

唯一的问题在于层数.考虑你需要先读一下指针所指的位置,再用$\delta$转移,这个东西就会很复杂.现在我们尝试用一个oblivious图灵机:它的转移不依赖指针指向的位置,这样大概就行了吧......

下面来看怎么证明$SAT\leq_p 3SAT$.考虑缩减一下这个东西,如果$C_i=A_i\lor B_i$,其中$C_i$的变量数量超过了$3$,而$B_i$的变量数量为$2$.引入一个新的变量$u$,转化为$C_i=(A_i\lor u)\land (B_i\lor (\lnot u))$.

一些汇总

本笔记原本是一门课的课程笔记, 但是很多东西都没及时记下来, 留到了后面汇总.

Undecidable Problems汇总

我们将展示下述undecidable problems:

  1. $UC(\alpha)=0\Leftrightarrow M_\alpha(\alpha)=1$.
  2. (recognizable)$HALT=\{\langle M,\alpha\rangle|M\text{ halts on }\alpha\}$.
  3. (recognizable)$A_{TM}=\{\langle M,\alpha\rangle|M\text{ accepts }\alpha\}$.
  4. $E_{TM}=\{\langle M\rangle|M\text{ accepts nothing}\}$.
  5. $EQ_{TM}=\{\langle M_1,M_2\rangle|L(M_1)=L(M_2)\}$.
  6. (Rice's Theorem)考虑$RE=\{A|\exists M,L(M)=A\}$,$\forall P,\emptyset\subsetneq P\subsetneq RE$,$T'=\{\langle M\rangle|L(M)\in P\}$ is undecidable.
  7. $ALL_2 = \{\langle M\rangle|\text{M is a CFG and }L(M) = \Sigma^*\}$.
  8. 波斯特对应问题(PCP):有限个字符串二元组$(s_i,t_i)$,要求从中选出若干个(可以重复选)$\{i_k\}$,使得$\sum_{k}s_{i_k}=\sum_{k}t_{i_k}$,问能否做到.

对于$UC$问题, 假设存在一个可以计算的图灵机$M$, 则应该有$M(\langle M\rangle)=UC(M)$, 然而这不可能, 因为$UC(M)$按定义就是$M(\langle M\rangle)$的取反.

对于$HALT$,假设存在一个图灵机$M$计算它,那我们实际上就可以decide $UC$: 你直接看一下是否停机, 要是不停机就直接跑就可以处理$UC$.

对于$A_{TM}$,很容易构造$UC\leq_m A_{TM}$.

对于$E_{TM}$,考虑证明$A_{TM}\leq_m\overline{E_{TM}}$,方法是:对一个$\langle M,\alpha\rangle$,造一个新的图灵机$M'$,使得只要$\alpha\ne \beta$,$M'(\beta)$就接受;否则跑$M(\alpha)$.这样就做到$A_{TM}\leq_m\overline{E_{TM}}$.

对于$EQ_{TM}$,考虑证明$A_{TM}\leq \overline{E_{TM}}$,方法还是造两个图灵机$M_1,M_2$,$M_1$只接受$\alpha$,$M_2$会拒绝所有和$\alpha$不同的,然后跑$M(\alpha)$.

最后我们来证明Rice's Theorem,显然只需要证明$T'$或者$\bar{T'}$有一个undecidable即可.不失一般性,我们下面假设$\emptyset$不满足$P$(如果满足,则可以将$P$转化为$\bar P$,将$T'$转化为$\bar {T'}$).此时证明$A_{TM}\leq_m T'$.现在我们假设:

  1. $\emptyset\notin P$.
  2. $L_1\in P,L(M_1)=L_1$
  3. $L_2\notin P,L(M_2)=L_2$.

对于一个$(M,\alpha)$,我们构造一个$M'$,对于一个输入的$\beta$,它先跑一下$M(\alpha)$:

  1. 如果$M(\alpha)$ accept: 跑$M_1(\beta)$,此时$L(M')=L_1\in P$.
  2. 如果$M(\alpha)$ reject: 跑$M_2(\beta)$,此时$L(M')=L_2\notin P$.
  3. 如果$M(\alpha)$死循环了, 此时$L(M')=\emptyset\notin P$.

于是这的确构造了一个足够的映射.

考虑证明$A_{TM}\leq \overline{ALL_2}$.考虑让$f(M,\alpha)$成为一个$CFG$,其识别所有字符串,除了$M(\alpha)$ accept时对应的转移$C_0-C_1-C_2-\cdots-C_n$.

先把$M$转化为单纸带.对每个字符$c$,创建它的一个对偶版本$c'$,表示当前指针指向了这个字符.

这里我们尝试让$C_i=(q_i,s_i')$,表示当前用到的纸带上面写的字符串是$s_i$,用对偶字符标出指针位置后为$s_i'$,状态为$q_i$.此外,为了我们下面的方便,我们假设$C'_i=f_i(C_i)$,其中$f_i(C_i)=\begin{cases}C_i&i\in \mathrm{even}\\C_i^R&i\in \mathrm{odd}\end{cases}$.

为此,考虑让该CFG能生成所有"并非"$M(\alpha)$的字符串,其包括:

  1. 格式不对的串.
  2. 初始$C_0$并非$\alpha$的串.
  3. $C_i$中包含多个对偶字符.
  4. 相邻的两个转移$(C_i',C_{i+1}')$不合法,即不满足$M$所刻画的转移.

我们尝试在CFG里插入上述规则,使得其能生成所有"至少一处"不合法的串.对于前两者,调整编码规则就可以让CFG足够生成.

对于(4),我们只需要插入一对不合法的$(C_i',C_{i+1}')$即可.由于它们一正一反,合法当且仅当有三个对应的字符(即:$C_i$时指针指向的字符,以及它旁边的两个字符)按$\delta$规则转移.因此只需要排栈就可以刻画.这样就足够了.

从而这的确证毕了我们想要的命题.

对于PCP问题,实际上是因为我们可以模拟configuration的变化.configuration的局部变化实际上是有限的,外部又可以通过拼$\Gamma$字符集的方式来模拟,因此容易证明$A_{TM}\leq_m PCP$.

NPcomplete问题汇总

我们来展示一些重要的NPcomplete问题的规约:

  1. 独立集(INDSET): 判断$\langle G,k\rangle$,$G$图中是否存在一个大小为$k$的独立集.

我们将展示$3SAT\leq_p INDSET$.

假设一个$3CNF$有$n$个变量和$m$个clause. 我们知道每个clause有七种赋值方式使得其成立,因此我们造一个$|V|=7m$的图,对每一个clause都造一个$K_7$表示其七种成功的取值.如果两种取值之间矛盾,那就在它们之间连一条边,这样最后的最大独立集大小$\leq m$,只需检查$\langle G,m\rangle$就可以判断.

  1. 点覆盖(Vertex Cover): 判断$\langle G,k\rangle$,$G$图中是否存在一个大小为$k$的点覆盖.

我们证明$INDSET\leq_p Vertex-Cover$,原因是注意到一个$\langle G,k\rangle$的独立集自然给出一个$\langle G,n-k\rangle$的点覆盖,反之亦然.

  1. $01$整数规划(IPROG):判断是否存在一种$x_i\in \{0,1\}$的赋值使得原不等式均成立.

我们将证明$SAT\leq_p IPROG$.这非常简单,因为你的bool函数本来就意味着不等式.

若干层次定理

在谈论层次定理之前, 务必需要先引入可构造的概念, 我们有:

  1. 空间可构造: 对于函数$f:\mathbb{N}\to\mathbb{N}$,其中$f(n)$至少是$\Omega(\log n)$级别. 如果存在图灵机可以在$O(f(n))$空间内将$1^n$转化为$f(n)$的二进制表示,则称$f$是空间可构造函数.
  2. 时间可构造: 对于函数$f:\mathbb{N}\to\mathbb{N}$,其中$f(n)$至少是$\Omega(n\log n)$级别. 如果存在图灵机可以在$O(f(n))$时间内将$1^n$转化为$f(n)$的二进制表示,则称$f$是时间可构造函数.

我们下面展示若干和层次有关的定理:

  1. Savitch定理: 对于任何函数$f$,满足$f(n)\geq \log n$,总有$NSPACE(f(n))\subseteq SPACE(f^2(n))$.
  2. 空间层次定理(对于单带图灵机): 对于任何空间可构造函数$f$,存在语言$A$可以在$O(f(n))$空间内判定,但不能在$o(f(n))$空间内判定.
  3. 时间层次定理(对于单带图灵机): 对于任何时间可构造函数$f$,存在语言$A$可以在$O(f(n))$时间内判定,但不能在$o(\frac{f(n)}{\log f(n)})$时间内判定.
  4. 电路层次定理: 对于两个函数$T,T':\mathbb{N}\to \mathbb{N}$,并且$T(n)\log T(n)=o(T'(n))$,则$SIZE(T(n))\subsetneq SIZE(T'(n))$.
  5. 非确定性时间层次定理: 对于任何时间可构造函数$f,g$,如果$f(n+1)=o(g(n))$,存在语言$A$可以在$O(g(n))$时间内判定,但不能在$O(f(n))$时间内判定.

让我们先看Savitch定理,它可以给出$NPSPACE=PSPACE$.

我们知道用$O(f(n))$空间的NTM,路径压缩一下一定会在$2^{O(f(n))}$步内结束.因此我们考虑直接模拟这个过程:我们现在的目标就是找到一条$C_{start}$到$C_{accept}$的路径,我们把这个问题记作$CY(C_{start},C_{accept},2^{O(f(n))})$,表示从$C_{start}$到$C_{accept}$是否能通过少于$2^{O(f(n))}$步到达.我们可以用分治的方式解决它:

对于当前问题$CY(C_1,C_2,t)$,枚举一个中间格局$C_m$,并判定$CY(C_1,C_m,\frac{t}{2})$和$CY(C_m,C_2,\frac{t}{2})$.

容易见到,每一层都需要$O(f(n))$的空间去枚举$C_m$和模拟,同时一共有$\log t=O(f(n))$层,所以总共只需要$O(f^2(n))$的空间.

我们来证明空间层次定理,方法是找到一个语言$A$,使其能在$O(f(n))$空间内判定,却不能在$o(f(n))$空间内判定.我们定义语言$A$为所有下述算法可以接受的输入$w$的集合:

  1. 对于输入$w$,要求其形如$w=\langle M\rangle 10^*$,其中$M$是一个图灵机的描述.
  2. 取$n=|w|$,并计算$f(n)$,划分出一段长度为$f(n)$的纸带.
  3. 在$w$上模拟$M$,并且统计当前使用的步数,如果超过$2^{f(n)}$则拒绝;如果模拟时用了超过$f(n)$长度的纸带也拒绝.
  4. $M$接受则拒绝,$M$拒绝则接受.

其中,仔细观察(3)的模拟:如果$M$需要$g(n)$空间运行,则模拟时显然只需要$Cg(n)$的空间模拟.

显然,上述定义同时给出了一个在$O(f(n))$空间内判定$x\in A$的算法,我们下面证明$A$在$o(f(n))$空间内不可判定.

假设存在图灵机$M$可以在$g(n)=o(f(n))$的空间内判定$A$,我们就可以用上述算法模拟$M$的结果(因为只需要$Cg(n)$的空间运行,只需要找到$n_0$使得$Cg(n_0)<f(n_0)$,然后输入$\langle M\rangle 1 0^{n_0}$):然而,$M$和上述算法会对同一个输入(即$\langle M\rangle 1 0^{n_0}$)上输出不同的结果,这立刻就导出了矛盾.

对于时间层次定理,证明方式和空间层次定理并无太大区别: 唯一的区别在于模拟. 我们断言模拟一个时间复杂度为$O(\frac{t(n)}{\log t(n)})$的图灵机需要$O(t(n))$的额外时间消耗即可.

为什么这里多了个时间消耗呢?这是因为当前场景下,图灵机模拟另一个图灵机的时候,另一个图灵机可以有足够多的纸带数量,但我们的模拟机却只有有限个,这就导致必须模拟的时候需要搬运信息.

最后来到电路上, 对于一个输入$\{0,1\}^n$,只考虑前$l=\log T(n)+2\log\log T(n)$个位置(也即只根据这$l$个位置确定取值).我们知道存在一个函数$f:\{0,1\}^l\to \{0,1\}$,使得其至少需要$\Omega(\frac{2^l}{l})=\Omega(T(n)\log T(n))$的时间,我们知道这也的确是一个精准的界,因此$T'(n)$的确可以模拟,这就搞定了.

最后来看非确定性时间分层定理, 我们考虑列举所有的NTM: $M_1,M_2,\cdots$,并且人为划分若干区间$[l_j,u_j]$,满足$u_j>l_j,u_{j}+1=l_{j+1},\log g(u_j)>f(l_j)$.此时,我们考虑一个新的图灵机$D$:它对于输入的$n\in [l_k,u_k]$:

  1. 如果$n\in [l_k,u_k)$,则输出$M_k(n+1)$的结果,但要求运行时间不能超过$g(n)$.
  2. 如果$n=u_k$,则输出$M_k(l_k)$的结果的取反.

现在假设有一个机子$M_k$可以在$O(f(n))$时间内模拟上述的$D$,由于$f(n+1)=o(g(n))$,因此它总能跑完,可以得到$M_k(l_k)=D(l_k)=M_k(l_k+1)=\cdots=M_k(u_k)=D(u_k)$,然而$D(u_k)$和$M_k(l_k)$是反着的,这就完蛋了.

coNL=NL的证明

众所周知, $NP$和$coNP$的关系至今仍是open problems. 然而对于空间复杂度类$NL$却有$NL=coNL$.我们下面将证明:由于$PATH$是$NL-complete$问题,而我们可以证明$\overline{PATH}\in NL$,从而真的有$NL=coNL$.

我们将首先说明$PATH$是$NL-complete$:显然$PATH\in NL$,此外对于任意$B\in NL$,我们将展示为何有$B\leq_l PATH$: 考虑非确定性图灵机$M(x)=1\Leftrightarrow x\in B$,由于它只能用logspace的空间,因此它的configuration只有多项式个,只需要让$PATH$判断是否有$C_{start}\to C_{accept}$的路径即可.

值得一提的是,尽管有向图可达性问题$PATH$是$NL-complete$的,无向图可达性问题$UPATH$却$\in L$.

下面我们来看$\overline{PATH}\in NL$的证明,我们想要找到一个算法$A$,使得$\exists u.A(\langle G,s,t\rangle,u)=1$当且仅当$s$在图$G$上不可达.

不妨定义$C_i$为从$s$出发,经过$\leq i$步后能到达的点的集合,初始设置$C_0=\{s\}$.我们下面造以下几种certificate:

  1. $u\in C_i$.
  2. $|C_{i-1}|=m\to v\notin C_i$.
  3. $|C_{i-1}|=m\to |C_i|=k$.

(1)只需要直接把这条路径写出来就行,容易在logspace下验证.

(2)的话,考虑当我们知道了$|C_{i-1}|$的大小,我们就可以直接给出这里面所有点的certificate, 对于每个$u\in C_{i-1}$,只需要检查是否存在$u$到$v$的边,就可以判断$v$是否在$C_i$里.

(3)的话,由于我们有前两种certificate,因此可以直接给出$n$个certificate,每个指示这个点到底在不在$C_i$中.

这样就可以判断是否有$t\notin C_n$,万事大吉.

P/poly与P和NP的关系

对证明$P\ne NP$的一个尝试方向是构造一个$NP$问题, 并证明能计算其的最小电路大小没办法做到多项式级别. 这是基于以下几种insight的:

  1. $P\subseteq P/poly$.
  2. 存在布尔函数$f$,其需要$\Omega(\frac{2^n}{n})$的电路大小才能计算.
  3. Karp-Lipton Theorem: 一旦$NP\subseteq P/poly$,则$PH=\Sigma_2^p$.

来看(2)的证明, 考虑布尔函数$f$的数量有$2^{2^n}$个,然而大小为$T$的电路只有$\leq (3\binom{T}{2})^T\leq (3T^2)^T$个,因此只有取$T=\Omega(\frac{2^n}{n})$才有希望计算所有的布尔函数.

此外, 这其实也是一个精准的界.我们可以证明所有的bool函数都可以被$\Omega(\frac{2^n}{n})$的电路计算.

考虑将输入的bit串分成两部分:前$n-k$个和后$k$个.现在考虑这个电路先看一眼前$n-k$个比特,然后决定一个$f_k:\{0,1\}^k\to \{0,1\}$的函数,再用这个函数计算后面$k$个比特.在该过程中:

  1. $f_k$只有$2^{2^k}$种.每个$f_k$可以被$k2^k$的size表示出来,因此用真值表只需$k2^k2^{2^k}$的size就可以把所有的$f_k$全写在电路上,并且让它们对着后$k$个比特各自算一个答案出来.
  2. 我们需要前$n-k$个比特去挑选一个答案.由于我们站在advice视角,我们可以直接造$2^{n-k}$个门,分别指示当前前面$2^{n-k}$个bit是什么情况,由于每读一个bit只需要往一侧递归,这实际上只需要$2^{n-k+1}$的大小就足够了,并以$2^{n-k}$的size就可以和(1)的结果做"与"后输出.

现在取$k=\log n-1$,此时第一部分的size为$k2^k2^{2^k}=(\log n-1)(\frac{n}{2})2^{\frac{n}{2}}\leq \frac{2^n}{n}$,当$n$足够大时.

现在我们来展示Karp-Lipton Theorem: 一旦$NP\subseteq P/poly$, 则我们可以证明$\Pi_2^p\subseteq \Sigma_2^p$, 从而$PH$塌缩到$\Sigma_2^p$.

考虑$\Pi_2^p SAT$问题: $\forall u\exists v\psi(u,v)$, 由于$NP\subseteq P/poly$, 我们知道$\Phi(u)=\exists v\psi(u,v)$这个问题实际上可以被一族电路$\{C_n\}$解决,使得$\Phi(u)=1\Leftrightarrow C_n(u)=1$.

而考虑事实上,如果我们把$v$拆成两部分:$v=v_1v_2$,那么$\Phi'(u,v_1)=\exists v_2\psi(u,v_1v_2)$同样也可以被电路判断,这就使得我们实际上可以用decision reduction去把这个$v$求出来!也就是存在一族电路$\{C_n'\}$,它可以做到$C_n'(u)=v$,使得$\Phi(u)=1\Leftrightarrow \psi(u,C_n'(u))=1$.

一个显明的思路是,直接用$\exists C_n'$从而把这个电路的描述encode进我们的formula中,但这样就需要额外一个描述去表达$\forall u.(\Phi(u)=1\Leftrightarrow \psi(u,C_n'(u))=1)$的性质.然而好在我们所想要的正是$\forall u\Phi(u)$,因此我们直接用$\forall u.\psi(u,C_n'(u))$即可.

最终,我们就转化出了$\exists C_n'\forall u\psi(u,C_n'(u))\in \Sigma_2^p$的形式,万事大吉.

此外,我们还想展示一个更有意思的定理:存在一个神谕$A$,使得$P^A\ne NP^A$,然而$NP^A\subseteq P^A/poly$.

考虑取$A=TQBF\coprod S$,或写作$A=\{0t|t\in TQBF\}\cup \{1s|s\in S\}$,其中$S$是一个稀疏语言,满足$\forall x,y\in S,x\ne y\Rightarrow |x|\ne |y|$.考虑一个语言$U(S)=\{1^n|\exists x\in \{0,1\}^n,x\in S\}$.容易发现总有$U(S)\in NP^A$,原因是只需要把这个$x\in \{0,1\}^n$作为certificate给出即可.

下面我们证明$NP^A\subseteq P^A/poly$.为此考虑$NP^{A}\subseteq PSPACE^S$,而至少$PSPACE/poly\subseteq P^{TQBF}/poly\subseteq P^A/poly$.于是我们只需要证明$PSPACE^S\subseteq PSPACE/poly$.

考虑左侧,其在运行的时候只能查询长度$\leq p(n)$的$S$,而能让oracle返回true的串只有$p(n)$个,我们可以把它们全部硬编码到电路中.从而已经证明了$PSPACE^S\subseteq PSPACE/poly$.

现在来看证明存在一个满足上述条件的语言$S$,使得$U(S)\notin P^A$,从而证明$P^A\ne NP^A$.

考虑列举所有的$\{M^A_i\}$图灵机,设$M^A_i$的运行时间为$f_i(n)$,我们力图找到一个语言$S$使得这些图灵机全都识别不了.我们先取一个语言$S=\{0,1\}^*$,后面我们会逐渐删去里面的元素.下面取$n_{0}=0$.

对于$M^A_i$,我们问它$1^{n_i}$能否accept,其中$n_i$满足$2^{n_i}\geq \sum_{j=1}^i f_j(n_i)$,由于右侧仍然是个多项式函数,因此这总能做到.然后我们删掉$S$中所有长度在$[n_{i-1}+1,n_i-1]$的串.现在,$M^A_i$会查询若干个字符串.如果该字符串长度$<n_i$,我们就按照目前的$S$回答;如果该字符串长度$\geq n_i$,我们全部回答no(顺便在$S$里删掉它问的东西),由于它是多项式复杂度的,我们对$n_i$的限制保证了长度为$n_i$的串最后总会剩下非零个.

现在,如果$M_i^A$回答yes,那我就把长度为$n_i$的从$S$中全杀了;如果回答no,那我就留一个剩下全杀了,这样这个$M_i^A$就至少回答不对长度为$n_i$的结果.

BPP在哪些复杂度类中?

容易根据定义直接看到$BPP=coBPP$以及$ZPP\subseteq RP\cap coRP$. 我们下面将展示三个更厉害的结论:

  1. $BPP\subseteq P/poly$.
  2. $BPP\subseteq \Pi_2^p\cap \Sigma_2^p$.
  3. $BPP\subseteq ZPP^{SAT}$

下面我们先证明$BPP\subseteq P/poly$,问题在于我们想要一个advice $r_n$,使得它对所有的输入$x,|x|=n$都能用.

考虑error reduction, 我们知道存在一个概率图灵机$M:\{0,1\}^n\times \{0,1\}^m\to \{0,1\}$,使得$\forall x\in \{0,1\}^n,Pr_{r}[M(x,r)\ne L(x)]<2^{-(n+1)}$.

也就是说,固定一个$x$,至多只有$\frac{2^m}{2^{n+1}}$个$r$是坏的,那么对于所有$x$,至多只有$\frac{2^m}{2^{n+1}}\times 2^n=2^{m-1}<2^m$个$r$是坏的,这就说明存在一个$r$对所有的输入$x$都是好的,它就是我们的advice.

下面我们证明$BPP\subseteq \Pi_2^p\cap \Sigma_2^p$,由于$BPP=coBPP$,我们只需要证明$BPP\subseteq \Sigma_2^p$即可,也即转化为$\exists u\forall vM(x,u,v)$的形状.也就是说:如果$x\in L$,则我们需要找到一个$u$,使得其可以控制住所有的$v$;否则,如果$x\notin L$,则每个$u$都存在不被它控制的$v$.

我们知道随机性来自于$\forall$,我们这么设计一个$\Sigma_2^p$中的问题:

$$ \exists u_1,\cdots, u_k,\forall r\in \{0,1\}^m,\lor_{i=1}^k M(x,r\oplus u_i) $$

下面我们来证明它的确可以和BPP中的问题互相转化:

用error reduction我们知道:

$$ \begin{aligned} x\in L&\Rightarrow Pr_r[M(x,r)=1]>1-\frac{1}{2^n}\\ x\notin L&\Rightarrow Pr_r[M(x,r)=1]\leq \frac{1}{2^n} \end{aligned} $$

当$x\notin L$时, 我们需要找到一个$r$,使得无论怎么选取$u_1,\cdots,u_k$,都拿不到任何一个$M(x,r\oplus u_i)=true$.这实际上是简单的,因为能让某一个$u_i$成功的$r$只有$\frac{2^m}{2^n}$个,总共也只有$k2^{m-n}$个.

当$x\in L$时, 我们需要找到一组$\{u_1,\cdots,u_k\}$,使得它们的确可以控制住所有的$r$.这个存在性证明可以使用概率方法,考虑对于一个固定的$r$:

$$ \begin{aligned} &Pr_{u_1,\cdots,u_k}[(\lor_{i=1}^k M(x,r\oplus u_i))=0]\\\ =& \left(Pr_{u}[M(x,r\oplus u)=0]\right)^k\\ \leq&\frac{1}{2^{nk}} \end{aligned} $$

因此,随机一组$u_1,\cdots,u_k$,存在一个$r$出问题的概率可以被Union Bound控制在$\frac{2^m}{2^{nk}}$上.

因此,如果我们能取$k$满足:

  1. $k2^{m-n}<2^m\Rightarrow k2^{-n}<1$.
  2. $\frac{2^m}{2^{nk}}< 1$.

就万事大吉, 取$k=\lfloor\frac{m-1}{n}\rfloor$即可(假设$m>n$).

最后我们来证明$BPP\subseteq ZPP^{SAT}$.回忆到$BPP\subseteq \Sigma_2^p$的证明,在那个证明中,我们需要选取一个$k$,使得:

  1. $k2^{-n}<1$.
  2. $2^{-kn}<2^{-m}$

我们就能把任何一个判断是否有$x\in L$,其中$L\in BPP$的问题,转化为一个$\exists u_1\cdots u_k,\forall r,\lor_{i\in [k]}M(x,u_i\oplus r)=1$的问题.

注意到(2)的目的是因为有:$Pr_{u_1,\cdots,u_k}[\exists r(\lor_{i\in [k]}M(x,u_i\oplus r))=0]\leq 2^{m-kn}<1$,从而证明存在这么一组$\{u_1,\cdots,u_k\}$.因此,如果一台机器选择去猜一组$\{u_1,\cdots,u_k\}$,它猜错的概率也就是$2^{m-kn}$.

现在我们这么造一台在$ZPP^{SAT}$的图灵机:我们让它每次去猜$\{u_1,\cdots,u_k\}$,然后去在$SAT$里判断是否有$\exists r,\lor_{i\in [k]}M(x,u_i\oplus r)=0$.如果有的话就重新猜,不然的话就接受.猜错一次的概率仅有$p=2^{m-kn}$,只要选取$k=n$,就可以使这个$p<\frac{1}{2}$.因此猜错的期望次数只有$\sum_{i=0}^{+\infty}(1-p)p^i=O(1)$次,每次猜测都是多项式时间复杂度.此时只要$x\in L$,我们立刻就能在期望多项式时间内猜出正确答案.

现在的问题在于当$x\notin L$时,如何在期望多项式时间内输出No.这并不困难,由于$BPP=coBPP$,我们可以同时去并行地猜$x\in \bar L$.由于要么$x\in L$,要么$x\in \bar L$,因此这么并行猜的期望时间仍然是多项式级别.

最后我们可以谈及一种$BPP$的变种:我们知道$BPP$的选择概率是均等的$\frac{1}{2}$,如果我们把这个概率改成$p\in (0,1)$,不妨设新的复杂度类为$BPP'$,那么$BPP$和$BPP'$的关系如何呢?

我们会展示以下三个结论:

  1. $BPP\subseteq BPP'$.
  2. 当$p\in \mathbb{Q},BPP=BPP'$.
  3. $\exists p,BPP\subsetneq BPP'$.

我们首先展示$BPP\subseteq BPP'$. 考虑对于$L\in BPP$,$M$是判断$L$的一个PTM,现在我们考虑构造一个$M'$,使得其满足题中的定义,并且$M'$也可以高概率判定$L$.

我们构造$M'$的方式是:每次连续随机两次:

  1. 如果结果是$10$,则模拟$M$的$\delta_1$.
  2. 如果结果是$01$,则模拟$M$的$\delta_2$.
  3. 如果结果是$00$或者$11$,则重新随机.

此外,我们在$M'$里加一个计时器,对于长度为$n$的输入,如果第(3)步的重复随机超过了$q(n)$次,我们就直接输出$0$,设这个事件为$A$.由于$10$和$01$出现的概率相等,因此只要没出现事件$A$,得到的结果就一定和$M$相符合.因此$Pr[M'(x)=L(x)]\geq Pr[M(x)=L(x)]-Pr[A]$.只要我们能说明右边是一个$>\frac{1}{2}+\delta$的数,其中$\delta$是一个常数,就可以用error reduction得到$\frac{2}{3}$的正确率.下面我们只要能限制$Pr[A]<\frac{1}{6}-\delta$即可.

现在我们来看在某个时刻,第(3)步连续出现$C$次的概率:为$(p^2+(1-p)^2)^{C}$.假设$M$的运行时间为$t(n)$,根据union bound,至少出现一次的情况就是$\leq t(n)(1-2p+2p^2)^{q(n)}$.容易见到只要取$q(n)=Ct(n)$,这一概率就是$o(1)$级别的,因此只要取足够大的$C$就可以.

当$p\in \mathbb{Q}$时,不妨设$p=\frac{a}{b},a,b\in \mathbb{N}_+$.考虑取$k\in \mathbb{N}$使得$2^{k-1}<b\leq 2^k$.注意这里的$k$是一个常数,我们接下来考虑用判定BPP中语言的$M$去模拟一个判定$BPP'$中语言的$M'$,以来证明$BPP'\subseteq BPP$,并根据(1)得到二者相等.

我们考虑每次让$M$随机$k$次,并且:

  1. 对于其中字典序最小的$a$种结果,采用$M'$的$\delta_0$.
  2. 除了上述以外,对于其中字典序最小的$b-a$种结果,采用$M'$的$\delta_1$.
  3. 对于剩下的$2^k-b$种结果,重复以上步骤.

同时仍然加一个计数器,当(3)重复了$q(n)$次后就直接输出$0$.

和上面的分析完全类似,此时(3)出现一次的概率是$\leq t(n)(1-\frac{b}{2^k})^{q(n)}$.取$q(n)=Ct(n)$就可以得到这个概率为$o(1)$,取足够大的$C$就可以模拟.

最后,考虑这样的$(0,1)$内的实数:不妨设它的二进制小数表示为$a_1a_2a_3\cdots$,它自己就是$\sum_{i\geq 1}a_i2^{-i}$.其中$a_i\in \{0,1\}$,并且满足$a_{4k+1}=0,a_{4k+2}=1$.容易见到这样的实数个数仍然是$2^{\mathbb{N}}$,也即不可数个.所以其中一定存在不可计算数$p$.我们下面来证明对于这个$p$来说,$BPP\subsetneq BPP'$.

我们构造这样一个语言$L=\{1^n|\text{二进制数n是p的二进制表示的前缀}\}$.我们证明$L\in BPP'$,但$L\notin BPP$.

先证明$L\in BPP'$,考虑取$k=\lceil\log_2 n\rceil$,也就是$n$的位长.我们直接让一台PTM随机$2^{12k}=O(n^{12})$次,每次如果是$\delta_1$就写下一个$0$,如果是$\delta_0$就写下一个$1$,然后统计写下来的数字中$1$的个数,设为$X$.立刻见到$E(X)=2^{2k}p$.我们接下来取$X$的前$k$位,并将它与$n$比较,如果相等则接受,如果不相等则拒绝.

由于我们上面对$p$的二进制位进行了一定的限制,我们知道如果$X$的前$4k$位不等于$a_1\cdots a_{4k}$,则要么至少多算了$2^{8k}$个$1$,要么至少少算了$2^{8k-1}$个$1$.

容易见到,当$|X-E(X)|\geq 2^{8k-1}$才会发生判断错误.根据Hoeffding引理,我们知道: $$ P(|X- E(X)|\geq 2^{8k-1})\leq 2e^{-\frac{2^{16k-1}}{2^{8k}}}=o(1) $$ 接下来我们来证明$BPP$没办法判定这个问题.假设$BPP$可以判定这个问题,我们可以构造一个确定性图灵机$M$,它的目的是枚举$BPP$的所有可能的运行结果.可以见到$M$可以在有限时间内判定这个问题.既然如此,我们直接枚举$p$的前缀二进制串并不断用$M$判断就可以计算$p$,但这不可能,因为$p$是不可计算数.

XOR不在AC0中的证明

写这篇博客的动机是我正在复习《计算理论导论》一课, 然后我想起来课上讲过的一个非常大的定理: $XOR \notin AC_0$,这个定理的重要推论是由于$XOR\in NC_1$, 以及显然的$NC_0\subsetneq AC_0$, 因此得到了$NC_0\subsetneq AC_0\subsetneq NC_1$. 然后我想默写一遍这个定理的证明当复习x.

我们下面来证明这个定理, 也许需要事先解释一下的是, $XOR$问题是指的构造一个电路使其能做到把$n$个bit异或起来. $AC_0$指的是只能用常数层多项式大小的电路, 但是每个电路门(与,或,非)都可以有任意多个输入.

证明该定理的主要思想是反证, 假设存在一个$AC_0$电路可以实现$XOR$, 考虑随机固定一部分电路输入, 那么对于那些"未被固定"的输入, 这个电路的功能应该还是要么是$XOR$, 要么是$XOR$后再反转.

我们首先对这个电路进行一些标准化, 用德摩根律可以轻易将$\lnot$挪到最下面一层,这样这个电路的形状就是$\land$和$\lor$交替,然后最下面有一层$\lnot$.

现在考虑随机固定一部分变量的值, 我们考虑一个$s$-restriction 函数$\alpha$,它的生成过程是: 先在$n$个位置中随机$s$个位置, 把剩下的$n-s$个位置等概率随机固定成$0$或者$1$. 我们把$f$固定后的结果为$f|_\alpha$.

我们考虑这个电路的一棵决策树, 不妨设$DT(f)$表示能计算$f$这个函数的深度最小的决策树,

我们先来展示一个引理:

如果$DT_{depth}(f)\leq d$,那么$f$有一个宽度$\leq d$的CNF/DNF形式.

这实际上是显然的, 因为你只需要把这棵决策树的每一条到叶子节点为$true$的路径全抄下来就行.

现在我们来展示整个证明中最重要的引理:

Switching Lemma: 假设$f$是一个$w$宽度的DNF或者CNF, 考虑一个$s$-restriction $\alpha$, 其中$s=\sigma n\leq \frac{n}{50}$, 则$Pr_\alpha[DT_{depth}(f|_\alpha)>d]\leq (C\sigma w)^d$.其中$C$是一个常数(取$17$应该就够了).

也就是说, 随机固定几位后,这个决策树的高度仍然很大的概率非常小.

这个switching lemma的意义是什么呢? 考虑我们一开始假设存在的那个计算XOR的$AC_0$电路,我们可以把其最下面一层(假设是CNF),通过固定若干位的方式, 转化成一个width并不明显变化的DNF, 从而和上层进行合并使得层数$-1$,由于只有常数层, 因此当$n$足够大的时候, 我们一定可以剩下一个单独的CNF或者DNF,它仍然要对无穷多个输入bit计算XOR或者XOR取反. 然而CNF和DNF都是只关注一个局部信息(比如有一个clause为真那DNF就是真,有一个clause为假那CNF就为假),但是XOR关注的是全局信息(只要有一个bit输入不确定,那么答案就不确定), 因此这必然不可能做到.

具体参数的选取,我们会在后面涉及.下面我们来证明这个Lemma.

所有的restriction的数量显然是$\binom{n}{s}2^{n-s}$,而且它们都是等概率被选取的. 现在考虑设集合$B$为"坏的restriction", 也就是$B=\{\beta|DT_{depth}(f|_\beta)>d\}$. 我们下面说明这个$B$的大小足够小.

假设$f=T_1\lor \cdots\lor T_m$. 现在我们来看对于一个$T_i$来说:

  1. 如果$T_i=0$,说明其中存在一个literal取$0$.
  2. 如果$T_i=1$,说明其中所有的literal都取$1$.

现在我们来看如果$DT_{depth}(f|_\beta)>d$了会发生什么,由于我们的定义,这意味着任何一个计算$f|_\beta$的决策树的深度都$>d$,我们下面挑一个好分析的:

考虑如此构造决策树: 对于$f$中那些还没确定的第一个clause,去直接造它的一棵决策树,这个决策树有一个(也可能没有)叶子节点会使得它为$true$,那就不用继续走了;对于剩下的为$false$的叶子节点,继续下一个clause的决策树构造,贴在这个节点下面.

我们知道这棵决策树的深度肯定$>d$,我们现在取它的第一条长度$>d$的路径的前$d$位,这就拿到了一个fix了$n-s+d$个变量的赋值方法,但我们注意到$\binom{n}{s-d}2^{n-s+d}<<\binom{n}{s}2^{n-s}$, 如果我们能用这种赋值配合上一些额外信息去还原回$\beta$呢?那我们实际上就造出了一个双射, 这个双射的右侧(使得上面那种特殊决策树的深度$>d$的$\beta$)是一个$\geq|B|$的集合,如果我们能说明它的左侧足够小,就可以说明$|B|$足够小.

我们现在的目标就是,发给对方一个$s-d$-restriction $\pi$以及一些额外信息,要求对方还原出唯一的$\beta$.

这个怎么做呢,考虑对于$\beta$已经确定的那些位置,让$\pi$取相同的值,现在对方只需要知道$\pi$中哪些位置是我们后续赋值的即可.

如果直接标注这些位置的话,每个位置需要$\Theta(\log n)$的长度编码,总共需要$\Theta(d\log n)$,那么额外的信息就需要$\Theta(n^d)$,这有点太差了.

现在考虑一个更好的编码:我们想让每个位置需要的长度从$\Theta(\log n)$降到$\Theta(\log w)$,方法是让它可以迅速确定我们在讨论哪个clause,这样就可以通过这个literal在clause里的位置确定它的位置.

怎么做到呢?我们来看一下原本的$f=T_1\lor \cdots \lor T_m$,而$f|_\beta=T_1^*\lor \cdots \lor T_l^*$,我们要额外赋值的肯定是在$T_i^*$里的东西(这里有一个问题是:如果一个变量$x$自己虽然没被赋值,但它所在的所有clause $T_i$都已经因为其它的赋值变成$0$了怎么办呢?如果这样的话这个证明立刻成功了,因为我们这个是一个XOR,它不可能忽略任何一个自由变量).因此如果我们能逐个确定这些$T_i^*$是哪个$T_j$,我们就可以用更小的编码实现这一切.

方法是,考虑在$\beta$的赋值的基础上多fix几位成为$\pi$,由于$\beta$并没有直接确定整个DNF的取值,因此一定不可能存在$T_j$被$\beta$变成$true$了,我们直接让$\pi$把$T_1^*$变成$true$,这样解码方拿到$\pi$,把它放在$f$上跑一遍,得到的第一个$T_j=true$就是$T_1^*$.然后它就可以通过辅助的东西(告诉它这个里面是哪些位置原本是自由变量)还原这一切.

可是然后怎么处理$T_2^*$呢?我们注意我们一定要保证还原出来的$\beta$存在我们刚刚所说的那一条长度为$d$的路径,因此我们需要保证还原出来的$s-d$-restriction一定尚未确定整个$f$的取值,这就需要额外信息告诉:这条长度为$d$的路径在$T_1^*$上的取值.然后就可以继续按照上面的方式继续操作.

现在我们完成了这一切,只需要$\Theta(d\log w)$的额外长度,因此总共的概率一定小于等于(用斯特林公式):

$$ \begin{aligned} Pr&\leq \frac{\binom{n}{s-d}2^{n-s+d}(Cw)^d}{\binom{n}{s}2^{n-s}}\\ &\leq \left(\frac{s}{n-s+d}\right)^d(2Cw)^d\\ &\leq \left(\frac{\sigma}{1-\sigma}\right)^d(2Cw)^d \end{aligned} $$

让$\sigma$取得足够小就可以获得我们的Switching Lemma.

最后的收尾就是,取$w=\Theta(\log N)$,其中$N$是电路大小,考虑不断操作后会剩下大概$n'=\Theta(\frac{n}{\log^k N})$,其中$k$是电路深度.

如果最后某一个clause的width$<n'$,那只需要确定这个clause的width个变量就可以确定整个的取值,这显然不符合XOR的性质.因此$w=\Theta(\log N)\geq n'$,这导出$N=\Theta(2^{\sqrt[k]{n}})$,这是一个远大于$poly(n)$的量级, 因此矛盾了.

IP=PSPACE的证明

显然, 由于prover可以模拟verifier的行为, 因此$IP\subseteq PSPACE$.我们下面将展示另一个方向:$PSPACE\subseteq IP$,方法是展示$TQBF\in IP$.

具体而言,我们会将一个$TBQF$问题转化为一个$IP$中的问题, 此外我们转化过程有以下特性:

  1. 如果$f\in TQBF$是可以成立的,那么转化后的$IP$问题一定会接受.
  2. $IP$的验证过程实际上是public coin的,也即:即使prover看到了verifier的随机结果,它也难以造假.

现在考虑一个$TQBF$问题$\psi=Q_1x_1\cdots Q_nx_n\phi(x_1,\cdots,x_n)$,我们知道任何一个公式其实都可以改成一个多项式,方法是$a\land b$改为$ab$,$\lnot a$改为$1-a$,因此我们可以把上述这个问题改为一个多项式判定的问题,现在我们要判定$f=\land_{b_1\in \{0,1\}}\lor_{b_2\in \{0,1\}}\cdots P_{\phi}(b_1,\cdots,b_n)$是否为$1$即可.

在最开始的时候,prover先给verifier发一个大素数$p\in (2^{2n},2^{3n}]$,verifier用Miller-Rabin验证一下这个$p$确实是素数,然后我们开始后面的过程:

我们下面展示这个证明最重要的设计:sumcheck protocol.简单来说,对于一个多项式$g$,以及一个常数$k$,每次prover都试图递归地向verifier宣称:

$$ k\equiv \land_{b_1\in \{0,1\}}\lor_{b_2\in \{0,1\}}\cdots g(b_1,\cdots,b_n)\pmod p $$

(注意,虽然对于我们的初始多项式,它的取值只有$\{0,1\}$两种,但我们后面会引入更多复杂的多项式,它的取值会更丰富一些)

此外,prover还会给verifier发一个多项式$s$的描述,并且宣称:$s(x)=\lor_{b_2\in \{0,1\}}\cdots g(x,\cdots,b_n)$.

现在,verifier首先要做的就是检查是否有$s(0)\lor s(1)\equiv k\pmod p$,如果没有的话直接拒绝.否则,verifier随机选取一个$a\in F_p$,并计算一下$h_a(b_2,\cdots,b_n)=g(a,b_2,\cdots,b_n)$的表达式.要求prover继续证明:

$$ \begin{aligned} s(a)&=\lor_{b_2\in \{0,1\}}\cdots g(a,\cdots,b_n)\\ &=\lor_{b_2\in \{0,1\}}\cdots h_a(b_2,\cdots,b_n) \end{aligned} $$

现在我们来看prover,如果它是个好人,那他就不必全程造假,此时一旦该formula确实可满足,那它就会全程回答正确的答案,并且一路通过.可如果它是个坏人,该formula不满足,它就需要开始造假.

我们来看一下什么时候prover可以造假成功,如果当前面对的是最后一步,并且实际上:

$$ k\not\equiv \land_{b_1\in \{0,1\}} g(b_1)\pmod p $$

那此时verifier只需要检查一下$g(0)\land g(1)$就可以发现prover在说谎! 当场就拿下了.

而如果在中间的步骤呢?prover显然不敢发一个真正的满足$s(x)=\lor_{b_2\in \{0,1\}}\cdots g(x,\cdots,b_n)$的多项式$s(x)$过去,不然verifier立刻就可以检查$s(0)$和$s(1)$判断对方在说谎.因此,prover必须伪造一个多项式$s'(x)\not\equiv \lor_{b_2\in \{0,1\}}\cdots g(x,\cdots,b_n)$.

此时,verifier随机一个$a$,如果随机后的结果满足$s'(a)=\lor_{b_2\in \{0,1\}}\cdots h_a(b_2,\cdots,b_n)$,那prover就赢麻了,它后面只需要一直说实话就可以让verifier承认它一开始的命题.可是如果$s'(a)\neq\lor_{b_2\in \{0,1\}}\cdots h_a(b_2,\cdots,b_n)$,prover就不得不继续说谎.

因此,prover成功说谎的概率,就是中间存在某一处选到了能使两边真正相等的$a$.不妨设这个多项式的次数为$d$,我们知道它实际上只有$d$个根,因此说谎成功的概率就不超过$n\frac{d}{p}$,而多项式的次数是$2^n$级别的,因此这个概率就被控制在了$\leq \frac{n}{2^n}$,这就搞定了.