二次非剩余

你是否想过如下问题：怎样向色盲证明两只袜子的颜色是不一样的？怎样证明两个图是不同构的？怎样证明一个数是二次非剩余的？咋听起来觉得很有意思吧，色盲是区分不了颜色的，怎么能让他相信两只袜子的颜色不一样呢。图同构问题目前既没有被证明属于P，也没有被证明属于NP-Complete。二次非剩余问题也没有被证明属于NP。这些听起来很“难”的问题，却可以通过交互式证明进行证明，下面先通过“向色盲证明两只袜子的颜色不同”这个有趣的例子一窥交互式证明的强大。向色盲证明两只袜子的颜色不同 P有一只红袜子和黄袜子，她的一个色盲朋友V不相信P的袜子颜色不同，P如何才能让V相信这是真的呢？一个简单的办法如下： P把两只袜子给V，V每只手拿了一只袜子 P转过身背对V V抛一枚硬币，如果头面朝上，则保持两只袜子不动，否则交换左右手的袜子 P转过身，V问P是否交换过袜子如果P回答错误，则V不相信；否则，重复100次实验，如果P都回答正确，则V相信这两只袜子是不同颜色的如果两只袜子的颜色确实不一样，则P通过区分两只袜子的颜色能正确回答V有没有交换过袜子。但是如果两只袜子颜色一样，则不管V有没有交换过，P都无法分辨这两只袜子，所以只好猜V有没有交换，而猜对的概率只有1/2，重复100次，都猜对的概率只有$(1/2)^{100}$，这是一个非常小的数，可以认为几乎不会发生，即出错的概率极低。这就是交互式证明的一个例子，上述证明有三个特点：1）交互过程，整个证明需要P和V进行交互才能完成；2）具有随机性，即V需要抛一枚硬币，来决定是否交换袜子；3）零知识，虽然V最终相信了这两只袜子是不同颜色的，但V还是不知道这两只袜子是什么颜色的。下面我们给出交互式证明的形式化定义。交互式证明（Interactive Proofs, IP）令$k$是$N\rightarrow N$的一个函数，我们称语言$L$属于$IP[k]$，如果存在一个$k(|x|)$多项式时间概率图灵机TM $V$，使得： $$ \begin{equation} \begin{cases} x\in L \Longrightarrow\exists P\quad Pr[V \text{ accepts }x, V(x)=1]\geq 2/3 \\ x\notin L \Longrightarrow\forall P\quad Pr[V \text{ accepts }x, V(x)=1]\leq 1/3 \end{cases} \end{equation} $$定义 $$IP=\underset{c}{\bigcup} IP[n^c]$$上述定义的第一条称为“完备性”（Completeness）：如果$x\in L$，则存在一个证明者P（prover），使得验证者V（verfier）能以多项式时间接受$x$，且接受的概率大于2/3；第二条称为“可靠性”（Soundness），如果$x\notin L$，则对于所有证明者P，V接受$x$的概率都不会超过1/3。对应到上面的例子，完备性：当两只袜子的颜色确实不同时，V接受的概率为1>2/3；可靠性：当两只袜子的颜色相同时，重复100次实验，V接受的概率只有$(1/2)^{100}<1/3$。 IP这个复杂性类就是所有IP[k]的并集。在IP中，P的能力是无穷的，但它不一定是诚实的；V能力较弱，只能进行多项式时间的计算。下面我们给出另外两个交互式证明的协议。图不同构（Graph Non-isomorphism, GNI）的交互式证明如果图$G_1$和$G_2$可以通过对顶点进行恰当标记来将它们转换为同一个图，则称$G_1$和$G_2$同构，记为$G_1\cong G_2$。换句话说，如果$G_1$和$G_2$同构，则在$G_1$的所有顶点标签上存在一个置换$\pi$使得$\pi (G_1)=G_2$，其中$\pi (G_1)$是将$\pi$作用到$G_1$的各个顶点上之后得到的图。下图就是两个同构图，右边给出了置换$\pi$。图同构的补集为图不同构（Graph Non-isomorphism, GNI），即判定给定的两个图是否不同构。下面是GNI的一个交互式证明过程。给定两个图$G_1$和$G_2$，证明者P想要向验证者V证明$G_1\ncong G_2$。 V：随机选一个$i\in \{1,2\}$，对$G_i$做一个随机的置换，得到新图$H$，则有$H\cong G_i$，将$H$发送给P P：发送$j$给V V：如果$i\neq j$，则拒绝；否则重复100次实验，都有$i==j$，则相信$G_1\ncong G_2$ 完备性：如果$G_1\ncong G_2$，则$H$只和$G_1, G_2$中的一个图同构，P因为能力无穷，一定能找出和$H$同构的图$G_j$，且满足$j==i$。 ...