第34章 解：（2）（2/2）

新笔趣屋【m.xbiquwu.com】第一时间更新《谎言与幻梦的二周目初见杀》最新章节。

说起来简单，可是因为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。