第34章 解:(2)(2 / 2)

说起来简单,可是因为SAT与QBF间横隔一个大境界差距,此过程无法在多项式时间内处理。

至少在围棋AI研究的早期,地球人尝试这条道路完全走不通。

好在拉斯有力大飞砖的超绝计算力,能帮徐林将这个转化变作现实。

徐林让拉斯做的第一件事就是这个:将珍珑棋局转为SAT问题,无论在难度还是形式上,都比原本更加简单。

想要零知识证明珍珑棋局,只需要零知识证明其相对应的SAT问题。

SAT虽只是NP之境,却也是NP巅峰大圆满,人称NP完全境。

SAT足以降维打击一切NP境以内的敌人。所有NP问题都可在多项式时间内化归为SAT问题。

零知识证明SAT,实际上就能零知识证明一切NP问题。

可实际上,徐林也没有直接处理SAT问题,而是转而寻求其他NP巅峰大圆满的高手。

同为NP巅峰大圆满,SAT与其他高手并没有区别,零知识证明任意一个NP完全问题都足以实现回推。

徐林求助的正是三染色问题:给定一张图G,求问能否用三种颜色给图G的所有端点染色,使得相邻顶点颜色不同。

(注:一张图是指一些顶点用一些线连接在一起。)

所有NP巅峰大圆满都可以在多项式时间内相互转化,SAT也可以按照某种规则转化为3染色问题。

这个转化可以如下粗浅理解:首先构造一个基本三角形,三个端点染色为“真”“假”“占位符”。

然后将所有的布尔变量与逻辑语句当做图的点,通过合适的方法连接在一起。

对这个图的三染色方案,实际上就是给每个布尔变量与逻辑语句赋值“真”“假”。

总而言之,零知识证明SAT,只需要零知识证明三染色问题。

与SAT不同,三染色问题的零知识证明是相当轻松的。

只需要在正确3染色的图上不停地抽查,验证每一次抽样所得边的左右两个端点颜色是否不相同即可。

可在神君的考验中,守碑人是一个恶意的检查者,他会试图用检查所得到的信息来破解徐林的染色方案,从而窃取珍珑棋局的正解。

也就是说,每一次进行边的抽样时,检查者都会获悉这条边两个端点的颜色情况。当他遍历徐林的3染色图时,一切信息便全部泄露。

小汐曾向徐林建言:“将答案隐藏在一些误导项之中”。

乍一听似乎没有可实现性,但3染色的零知识证明恰恰就是要用这般思路。

(汐:那为什么只夸思不夸我?)

假设徐林现在用红绿蓝三种颜色实现了图G的三染色。

他的下一步操作是:再准备一张图G,但这次把本该染红的地方染绿,把本该染绿的地方染蓝,再把本该染蓝的地方染红。

可以想象,在新得到的图里,相邻端点所染上的颜色依旧不同。

红绿蓝三种颜色有6种办法打乱,徐林总共可以制作6份图G的三染色副本。

每当恶意检查者抽查一条边时,徐林就随机抽取一个副本,将那个副本上的这条边透露给检查者看。

比如检查者看到这条边连接了一个红色端点与一个绿色端点。

那他能照抄答案,一个涂成红色,一个涂成绿色吗?

答案是不能。

因为他下一次抽查连接红色点的边时,就可能意外地发现:本该被染成红色的点,这次居然被染成了绿色?

对于任何一条边,两端点颜色的检查结果会在{红蓝,红绿,蓝绿,蓝红,绿红,绿蓝}中均匀地随机出现。

检查者唯一能确凿知晓的事项,仅有两端点颜色不同。

至此,三染色问题可零知识证明,进而一切NP问题都有零知识证明方案,其中包括围棋转化来的SAT。