趣题:怎样向别人证明两个图不同构?

若干个顶点(vertex)以及某些顶点对之间的边(edge)就构成了一个图(graph)。如果图 G 和图 H 的顶点数相同,并且它们的顶点之间存在着某种对应关系,使得图 G 中的两个顶点之间有边,当且仅当图 H 中的两个对应顶点之间有边,我们就说图 G 和图 H 是同构的(isomorphism)。直观地说,两个图是同构的,意思就是它们本质上是同一个图,虽然具体的画法可能不一样。下面的两个图就是同构的。其中一种顶点对应关系是: 1 – a, 2 – c, 3 – d, 4 – b, 5 – e, 6 – g, 7 – h, 8 – f 。

目前,人们还没有找到任何高效的算法,能迅速判断出两个图是否同构。在普通计算机上,判断两个图是否同构,这需要花费大量的时间。因此,人们经常以图的同构为例,来解释复杂度理论和现代密码学中的诸多概念。

假设你家里的计算机十分强大,能很快判断出两个图是否同构,还能在两个图确实同构的情况下,给出一种顶点对应关系。但你的同桌家里的计算机却非常弱,没法做什么大型运算。课堂上,老师向全班展示了两个很复杂的图,不妨把它们叫作图 G 和图 H 。老师布置了一个特别的选做题:判断出这两个图是否同构。每个同学都可以提交答案,答案里只需要写“是”或者“不是”即可。按时提交答案并答对者,期末考试会获得 5 分加分;按时提交答案但答错了的,期末考试成绩将会倒扣 30 分;不参与此活动的同学,期末考试既不加分也不扣分。显然,每个同学都不敢随意提交答案,除非百分之百地能保证自己获得的答案是正确的。回到家后,借助家里的超级计算机,你很快判断出了这两个图是同构的。你给你的同桌发送了信息:“我已经算出来了,这两个图是同构的。”但是,你的同桌却回复说:“你不会是骗我的吧?”你打算怎样说服他,这两个图确实是同构的呢?

你只需要把两个图的顶点对应关系发送给他即可。他家里的计算机非常弱,没法找出满足要求的顶点对应关系。但若有了一个顶点对应关系,验证其确实满足要求,这是非常容易的,几乎不需要什么计算量——只需要枚举图 G 里的顶点对,看看它们之间有边是否当且仅当图 H 中的对应顶点之间有边即可。完成验证之后,他就知道了,这两个图确实是同构的。

总结起来,刚才我们面对的是这样的困境:

  • 你拥有无限的计算能力。
  • 对方的计算能力非常有限。
  • 你想要向对方证明,图 G 和图 H 确实是同构的。

判断两个图是否同构可能很难,但若给出一段证据后,很容易验证两个图确实同构,上述困境也就得以解决了。这就是复杂度理论中 NP 问题的大致意思。

但是,如果把两个图同构的证据直接交给你的同桌,你的同桌或许又会用同样的办法去帮助别人,最后搞得班上所有人都获得了加分,这就没意思了。有没有办法说服你的同桌,这两个图确实是同构的,但却又让他无法拿到这两个图同构的证据呢?也就是说,现在我们面对的是这样的困境:

  • 你拥有无限的计算能力。
  • 对方的计算能力非常有限。
  • 你想要向对方证明,图 G 和图 H 确实是同构的。
  • 你不想泄露这两个图的顶点之间的对应关系。

这看上去似乎是不可能实现的——不把顶点之间的对应关系告诉对方,怎样说服对方两个图确实是同构的呢?然而,这竟然是能做到的。整个过程分为很多轮进行。在每一轮里,你随机生成一个与图 G 同构的图 G′ 。如果图 G 和图 H 真的同构,那显然图 G′ 也与图 H 同构。然后,你把图 G′ 发送给对方。对方可以随机提出下面两个要求之一:提供 G′ 与 G 同构的证据,或者提供 G′ 与 H 同构的证据。不管对方提出的是哪个要求,你都可以放心大胆地把证据发给对方,这不会泄露图 G 和图 H 之间的对应关系。另外,如果图 G 和图 H 不是同构的,那么这两个要求你不可能都做得到;面对对方的抽查,总能如约作答的概率是很低很低的。很多轮过去后,对方便慢慢确信,图 G 和图 H 真的是同构的了。在现代密码学中,让对方相信命题的正确性,但又不泄露任何其他的信息,这就叫作“零知识证明”(zero-knowledge proof)。

现在,让我们再来看一种情境。去掉上述第四点要求,但把第三点要求改一下:

  • 你拥有无限的计算能力。
  • 对方的计算能力非常有限。
  • 你想要向对方证明,图 G 和图 H 确实是同构的。

你打算怎么办?注意,你的办法应该普遍适用于一切情况。在某些特定的情况下,你当然可以告诉对方,“这两个图显然不同构,因为它们的边数就不一样多”,但这不适用于两个图的边数一样多的情况。

 

 

 

 

 

 

 

 

 

 

很简单。每次让对方随机生成一个与图 G 同构的图或者与图 H 同构的图,并把它发送给你。每次你都可以准确地告诉对方,刚才发来的图是从图 G 变过来的,还是从图 H 变过来的。多试几次,对方便能确信,这两个图确实是不一样的。

上述所有例子都属于“交互式证明”(interactive proof)。第一个例子是确定性的交互式证明(deterministic interactive proof)。它也是最简单的一类交互式证明。第二个例子则是带有附加条件的交互式证明。也就是说,零知识证明是一种特殊的交互式证明。第三个例子则表明,对于有些问题来说,交互式证明的存在性并不是显然的(即使没有任何附加条件)。如果利用确定性的交互式证明,你能向别人说明问题的答案是肯定的,我们就说这个问题属于 dIP 集合。很容易证明, dIP = NP 。如果利用交互式证明(包括非确定性的交互式证明),你能向别人说明问题的答案是肯定的,我们就说这个问题属于 IP 集合。交互式证明理论的一个最主要的结论就是 IP = PSPACE ,其中 PSPACE 表示所有能用多项式的空间解决的问题。

第一个例子和第二个例子都是我早已听说过的例子。第三个例子以及与此相关的交互式证明理论则是我最近在 Introduction to the Theory of Computation 一书中看到的。它们应该都是复杂度理论中非常经典的例子。

35 条评论

  • godultimate24

    第一次做沙发,先mark了

  • testmakercc

    第三个例子,如果G和H其实是同构的:

    每次让对方随机生成一个与图 G 同构的图或者与图 H 同构的图(于是这个新图总是既和G同构,也和H同构),并把它发送给你。每次你都可以准确地告诉对方,刚才发来的图是从图 G 变过来的,还是从图 H 变过来的(无论说哪个都是正确的)。

    于是还是无法证明G和H不同构?

    • Pa55er6y

      注意前提条件是你要向对方证明G和H不同构,所以你说的这个情况其实不需要考虑。
      退一步说,如果G与H同构,对方生成一个与G同构的图F,则你无法判断F到底是由G还是H生成的。一旦你的回答错误,对方就知道G和H其实同构,或者你在骗他。

    • youstupid

      既然同构了怎么可能知道图 G 变过来还是图 H 变过来?
      你脑子没事吧?

    • hillson

      前提是对方测试:我说G,H不同构,是不是在骗人。。。对方做了个G同构的图过来,如果我骗人,实际上G,H同构,则我有可能回复是H同构的,那就被发现我骗人了。。。

    • proton

      hillson正解

    • callG

      hillson:
      ”前提是对方测试:我说G,H不同构,是不是在骗人。。。对方做了个G同构的图过来,如果我骗人,实际上G,H同构,则我有可能回复是H同构的,那就被发现我骗人了。。。“
      实际上G,H同构,则我不可能回复是H同构的吧。。。

  • lunajrq

    AM和MA,非常有意思的内容。我们老师当时举的例子是说服色盲粉笔颜色。

    • 浣熊

      什么题什么题 说来听听吧

    • 浣熊

      好吧 我自问自答,就是只要这个色盲每次问别人粉笔的颜色 每次问的结果都一样 那命题就是肯定的。我理解的zero knowlege proof就是:尝试通过N次一致的结果证明这个命题是肯定的。

    • 浣熊

      但是我觉得这个色盲问题其实不能体现交互式证明这个概念

    • lunajrq

      一直没看回复,是这样的。
      有一个盲人,有两支粉笔,然后有一个人需要说服他两支粉笔颜色不同。
      盲人先用粉笔在黑板上画一个圆,如果两支粉笔颜色不同,另一个人一定可以每次都说对是哪支粉笔画的,否则另一个人不会有高于1/2的几率猜对

  • 依云

    零知识证明那个,把证明过程记录下来给别的同学看就好。他们也只需要证明不需要知识呀。

    • fakenerd

      注意 证明过程中
      对方可以随机提出下面两个要求之一:提供 G′ 与 G 同构的证据,或者提供 G′ 与 H 同构的证据。
      如果不具有计算能力的话,是无法满足这个要求的,因为只知道其中一个。

    • Zhaoyang

      “交互式证明”的“证明过程”不同于经典的“证明过程”。比如说我是原文中的“同桌”,我不知道正确答案,但是我可以自问自答、编几个回合的“证明过程”给“其他同学”看,“其他同学”不就被骗了嘛。

    • Qian Hong

      “把证明过程记录下来”的方法中,假定了同桌是诚实的。如果同桌跟“我”演双簧,一起骗其他同学的钱,那这个证明记录就不可靠了。零知识交互式证明中,最有价值的信息是“交互事件发生的顺序”。可靠的顺序是:“我”先发送同构图,同桌再生成随机数;如果双方串通,同桌先生成随机数,“我”再发同构图,那就可以伪造一份证明记录了。“事件发生的顺序”只有当事人和“上帝”知道,不在场的人是无法确认的,这就是为什么“交互”那么重要。

  • AES

    顾老师,能告诉我们为什么那么久没更新吗?

  • LQYMGT

    1. GI 问题的 zero-knowledge proof 已经属于 IP 而不是 dIP 了,因为 verifier 已经是 probabilistic;
    2. dIP 与 IP 的区别不在于答案的肯定性,在于 verifier 是 probabilistic 以及允许 verifier 得到错误的结论。

  • “交互式证明理论的一个最主要的结论就是 IP = PSPACE ,其中 PSPACE 表示所有能用多项式的空间解决的问题。” 比如问a! mod b的奇偶性,这是PSPACE吧,那怎么是IP了,即利用交互式证明(包括非确

    “交互式证明理论的一个最主要的结论就是 IP = PSPACE ,其中 PSPACE 表示所有能用多项式的空间解决的问题。”
    比如问a! mod b的奇偶性,这是PSPACE吧,那怎么是IP了,即利用交互式证明(包括非确定性的交互式证明),你能向别人说明问题的答案是肯定的

  • 王念一2001

    有生之年终于看到更新了……

  • 摇钱妹

    终于更新了,还以为你怎么了

  • 浣熊

    放假趣味读物 这博客真的很棒

  • 匿名

    M67,Pi节Conway发的那三道题求解答啊,尤其是最后一道

  • nengliangz

    找您不太容易噢,我看了你的演讲 唉,这个教育,里面一个例子,农药残留高于国家标准,里面说改成农药残留严于国标 ,但农残标准是规定的最低标准啊,所以只要符合国标的都严于国标,严于等于通过或符合,我觉得都有点过度宣传,臭不要脸了。,甚至欺骗。

  • 老黄

    最近居然如此频繁的更新…

  • 女性网

    算晕了,算术不好

  • w_2014

    零知识证明哟

  • 无大志

    第三个例子,我想到的办法:
    生成明显不同构的G’和H’(肉眼或弱计算机能识别)发给对方,对方随机要求证明其中哪个是G(或H)的同构,但不证明另一个;多次之后,对方相信G和H不同构。

    • 无大志

      修正一下:明确告诉对方G’是G的同构,H’是H的同构,但只按对方要求证明其中的一对

  • 无大志

    如果不用图这种纯数学的表述,这道题可以改为克隆同胞证明,验证一次就克隆一个

  • tonyyl

    G和G’同构,则G’和H也同构。那么如果同学能够判断其中一组是同构的,而你又告诉他另外一组的对应关系,那么G和H的对应关系不就直接出来了吗?

回复给 tonyyl 取消回复

3  ×    =  21