Tag Archives: 二次非剩余

有趣的交互式证明

你是否想过如下问题:怎样向色盲证明两只袜子的颜色是不一样的?怎样证明两个图是不同构的?怎样证明一个数是二次非剩余的?

咋听起来觉得很有意思吧,色盲是区分不了颜色的,怎么能让他相信两只袜子的颜色不一样呢。图同构问题目前既没有被证明属于P,也没有被证明属于NP-Complete。二次非剩余问题也没有被证明属于NP。

这些听起来很“难”的问题,却可以通过交互式证明进行证明,下面先通过“向色盲证明两只袜子的颜色不同”这个有趣的例子一窥交互式证明的强大。 Continue reading