2008-01-25 23:07| 
7 Comments | 本文内容遵从 今天在回访网站流量来源时看到了一个很牛B的东西，和大家分享一下。
给定一个顶点数为100000的图G，问是否存在Hamilton回路。现在，A宣称自己已经找到了一个Hamilton回路，但B不信，要A证明给他看。你能否想出一个办法使得，A可以让B相信自己有了正确的答案，但B依然不知道答案是什么。这种方法既科学又有趣，整个过程不需要第三者参与，仅仅靠AB两人之间的交流即可。这种方法可以让B有充分的理由相信A找到了Hamilton回路，但能保证B仍然得不到任何与正确答案有关的线索。
首先，A生成一个100000的全排列P，然后用这个排列P把原图G的顶点标号打乱（对标号进行置换），这样就得到了一个同构的图G'。然后A把图G'告诉给B。注意，目前判断两个图是否同构还没有有效的P算法，因此除非A把排列P也告诉了B，否则B不知道G'和G是不是真的同构。接下来B从下面这两个问题中随机抽一个问题让A作答：叫A证明G与G'同构（即叫A给出排列P，确保他没有作假），或者叫A指出G'中的一条Hamilton回路。反复进行“构造G'—抽问”的过程，每次A答对后B都会更加确信A确实找到了原图G的Hamilton回路，来个十几二十次后A作假的嫌疑基本上可以被排除了。这是因为，如果A不知道原图G中的Hamilton回路，这两个问题他是不可能同时答对的，既然B是抽查的，A不可能每次总能答对。同时，除非B同时知道了两个问题的答案，否则B永远不知道原图G的Hamilton回路是什么。仅仅知道G'的Hamilton回路是没有用的，因为此时B连G和G'是否同构都不知道，更别提找出它们之间的对应关系了。
来源：http://www.zju88.cn/cgi-bin/bbstcon?board=Algorithm&file=M.1200769543
7 条回复
您也随便说几句吧：
牛B的东西.. 学习了..
About Graph Isomorphism:
http://front.math.ucdavis.edu/0801.0398
can not understand
It seems a example of interactive proof system.
我说。这样都可以。。比较像统计中对敏感问题的统计方法，掷硬币：
正-->身份证号奇偶性
反-->问题答案。
2楼那个证明的好像被作者收回了...
[...] 在各种介绍密码学与协议的教材里都有关于零知识证明的话题——如何让你相信我已经找到了一个解，但又不告诉你这个解是什么。最经典的例子便是关于Hamilton回路的问题——存在这样一种巧妙的协议，可以让你相信我已经找到了某个图的Hamilton回路，而你却完全得不到任何关于这个Hamilton回路本身的任何信息。今天我又看到了一个非常不错的零知识证明实例。给定一个平面图，你需要给每个区域染一种颜色，使得任两个相邻的区域颜色不同。如果你仅用三种颜色就能做到这一点，我们就说这个图是可以三染色的。目前我们还没有一个判断平面图可否三染色的好办法，寻找一个平面图的三染色方案并不是一件容易的事。现在，假如你已经找到了某个给定平面图的三染色方案，你想向别人炫耀自己的成果，但又不想透露关于你的染色方案的任何信息。你能否设计一种协议使得对方能够相信你确实找到了一种三染色方案而又不告诉他这种方案是什么呢？ [...]