重庆邮政-北京司法考试办公室

若干个顶点（vertex）以及某些顶点对之间的边（edge）就构成了一个图
（g raph）。如果图 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 真的是同
构的了。在现代密码学中，让对方相信命题的正确性，但又不泄露任何其他的< br>信息，这就叫作―零知识证明‖（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 一
书中看到的。它们应该都是复杂度理论中非常经典的例子。