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

二境NP境，不可在多项式时间内求解，却可以在多项式时间内验证一个答案是否正确，就比如SAT。

第三境PSPACE境，可在多项式空间内求解，比如围棋、象棋各种棋，还有方才的QBF。

第四境EXPTIME境，可在指数时间内求解，比如各种广义游戏是否有必胜策略。

再往上的境界，已是不知天地为何物，恐怕只有神才知道。

QBF相比SAT，横跨一个大境界，一般情形下根本无法同台较量。

但是众所周知，尽管围棋死活题的复杂度达到PSPACE，可一个人依旧是可以做的。这个时候其实就用到一件事，那就是枚举对方可能策略，将一切可能性堵死。

QBF问题也是如此，完全可以通过枚举去掉逻辑语句中的“任意”，将他们全部改成存在。

徐林事先声明自己将在120手内取胜，看似提高围棋残局的难度，可实际上却简化了QBF求解，将搜索范围极大的缩小。

至多只有黑方60手，白方60手的相互交替。那么就可以通过枚举白方60手的对策，将QBF问题转化成低阶的SAT问题。

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

小主，这个章节后面还有哦，请点击下一页继续阅读，后面更精彩！