“且看相对简单的河图洛书，每个格子必属于九种状态之一，分别对应于数字1到9。而河图洛书的规则，实际上就是对有限种状态的约束。
第一种约束，是任意两个不同的格子，状态不同。
第二种约束，是任意三个直线相连的格子，状态组合必须属于以下八者其中之一：
(1,5,9),(1,6,8),(2,4,9),(2,5,8),(2,6,7),(3,4,8),(3,5,7),(4,5,6)。”
沈归尘似懂非懂地点点头。
“再看相对复杂的围棋，每个交叉点也只有三种可能的状态：【黑】、【白】、【空点】。只不过随着棋局的进展，每个交叉点的状态会动态地发生变化。
但无论怎样，围棋的几条规则，落子规则，提子规则，禁止自杀与打劫，其实都是关于棋盘总状态的约束。”
沈归尘觉得徐林说得对，但又不知道这有什么意义。
徐林总结道：“只涉及状态的赋值与状态间的逻辑约束，这实际上就是布尔代数问题。”
天元大陆土着听不懂思密达。
徐林所聊的，实际上就是围棋问题的抽象化。也即是拉普拉斯妖，又或者说AI们是如何处理这个问题的。
在简单的河图洛书问题中，拉斯会假定9个变量x_i，分别取值于数字1到9。
接下来她只需要找到一组合适的取值，使得以下的逻辑命题全部正确：
【对于?i≠j，x_i≠x_j】
【对于?{i,j,k}∈{{1,2,3},{4,5,6},{7,8,9},{1,4,7},{2,5,8},{3,6,9},{1,5,9},{3,5,7}}，
{x_i,x_j,x_k}∈{{1,5,9},{1,6,8},{2,4,9},{2,5,8},{2,6,7},{3,4,8},{3,5,7},{4,5,6}}】
这实际上就是boolean可满足问题(SAt)，是计算机有能力解决的一大类典型问题。可以直接用SAt求解器计算出结果。
对于围棋，完全可以做类似的事，将每个交叉点编码成变量x_{i,t}，取值范围是{黑，白，空点}。因为围棋是动态过程的缘故，变量x不仅依赖于位置i，同样依赖于手数t。
与河图洛书的处理办法相似，围棋规则可以全数转化成关于x_{i,t}的逻辑约束，进而使得残局求活同样转化成一个寻找x_{i,t}赋值，使得关于规则的逻辑语句全部成真的计算问题。
徐林世界的AI围棋搜索就在隐含地处理类似的逻辑推理。只不过它们并非做显式查找，而是用神经网络近似。
无论河图洛书还是数独，其实都是一个人的游戏，故而获胜条件是“存在”一组状态，使得所有规则约束被满足。
也即是说，本质都是SAt问题。
可围棋却是双方玩家对弈的游戏，想要获胜就必须“存在”黑方第一手，对“任意”白方第二手，“存在”黑方第三手，对“任意”白方第四手……最后都有x_{i,t}满足所有规则约束（包括黑方获胜的一条额外约束）。
这种“存在”“任意”的量词交替模式，决定了围棋是比SAt更高阶的问题——qbF（量化布尔公式）。
qbF的复杂度与SAt相比如隔天堑。至少以徐林那个世界的计算力，完全无法将围棋问题彻底解决。
当然，用拉斯开挂全秒了。
关于计算问题的难度，其境界划分大致为：
第一境p境，可在多项式时间内求解，包括排序算法、素性判断。
第二境Np境，不可在多项式时间内求解，却可以在多项式时间内验证一个答案是否正确，就比如SAt。
第三境pSpAcE境，可在多项式空间内求解，比如围棋、象棋各种棋，还有方才的qbF。
第四境ExptImE境，可在指数时间内求解，比如各种广义游戏是否有必胜策略。
再往上的境界，已是不知天地为何物，恐怕只有神才知道。
qbF相比SAt，横跨一个大境界，一般情形下根本无法同台较量。
但是众所周知，尽管围棋死活题的复杂度达到pSpAcE，可一个人依旧是可以做的。这个时候其实就用到一件事，那就是枚举对方可能策略，将一切可能性堵死。
qbF问题也是如此，完全可以通过枚举去掉逻辑语句中的“任意”，将他们全部改成存在。
徐林事先声明自己将在120手内取胜，看似提高围棋残局的难度，可实际上却简化了qbF求解，将搜索范围极大的缩小。
至多只有黑方60手，白方60手的相互交替。那么就可以通过枚举白方60手的对策，将qbF问题转化成低阶的SAt问题。
说起来简单，可是因为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。
《谎言与幻梦的二周目初见杀》无错的章节将持续在皮皮读书小说网更新,站内无任何广告,还请大家收藏和推荐皮皮读书！
喜欢谎言与幻梦的二周目初见杀请大家收藏：(m.pipidushu.com)谎言与幻梦的二周目初见杀皮皮读书更新速度全网最快。