当然，用拉斯开挂全秒了。

关于计算问题的难度，其境界划分大致为：

第一境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的所有端点染色，使得相邻顶点颜色不同。

（注：一张图是指一些顶点用一些线连接在一起。）