​ 10-5NP问题的零知识证明（二） 哈密顿回路问题 |密顿回路的定义 哈密顿难题 HC零知识证明性质分析 完备性： 如果证明者知道图G的哈密顿回路，他对于不同的α都可以做出正确的响应。显然，诚实验证者接收的概率为1。 可靠性： 如果证明者不知道图G的哈密顿回路，那么他只能够以1/2的概率欺骗验证者。这个概率可以理解为证明者预先猜测成功验证者α值的概率。即诚实验证者每轮拒绝的概率为1/2。 零知识性： 可知的是，当α=0时，V获取的仅仅是一个G的同构；当α=1时，V确实得到了对应图的哈密顿回路，但是与的映射并未泄露。所以，V仍然无法获取G的哈密顿回路。 ​