在计算机里面，对于多项式级别的时间，我们还是认为很快的。如果把问题按照求解的难度来进行分类的话，P 是指能够用多项式时间求解的问题，俗话说就是算起来很快的问题。NP 是指算起来不一定快，但是任何答案我们都可以检查起来很快的问题。NP 完全问题，是比所有 NP 问题都要难的 NP 问题。虽然人们有个美好的想法，总觉得验算起来很快的应该可以找到办法让他算起来很快，但目前还是个未知数。。。[7]
很不幸，求解一个扫雷游戏的解，正好是一个 NP 完全问题——在能够轻松验证结果是否正确的问题里面最难的那一类。 这一类问题目前为止人们还没有发现多项式时间的求解算法，通常只有指数级甚至阶乘级的搜索算法来解决。
用来显示液晶数字的逻辑电路。我们可以很方便地一个一个试，但是反过来却很难，尤其是在这个逻辑电路非常庞大的时候
扫雷游戏属于一个如此困难的问题，其原因就出在上一章提到的，可以把扫雷游戏看做一个个逻辑门进行运算的逻辑电路。给定一个逻辑电路，在已知输出结果的情况下，能否确定每个输入的值？这个问题被称为 SAT 问题，是世界上第一个被证明其为 NP 完全的问题。[8]这种问题验证起来非常容易，你只需要把结果代入到逻辑电路中，马上能知道是否符合要求，但倒过来想要计算符合结果的输入就极端地麻烦。
求解扫雷游戏的结果，利用那些构造的逻辑门，恰恰等价于求解 SAT 问题。[9]
扫雷还和渗透有关系
Percolation
液体，图片来自 Giphy，Michael Shillingburg
其实我们在玩扫雷游戏的时候觉得很难，其实还有另外一个原因。这个原因和物理里面的渗透还有关系。
在上个世纪 60 年代，科学家们 [10] 发现在流体流过多孔的介质的时候，介质中的空洞总是会被堵塞，有时候就会影响流体流出。更为奇怪的是，当这些多孔的介质的孔隙被随机堵塞的比例逐渐增大而达到某一值时，一开始一直能够流动的流体就突然被完全堵住。在孔洞被随机堵住的概率发生变化时，液体流过的比率也会发生一个突变。
这种现象被称为逾渗（percolation）。[11]
遇到这种情况，你该怎么下手
在扫雷里面，也存在类似逾渗的现象。当一盘游戏里面的地雷密度特别低的时候，我们差不多随便点，都不会点到地雷，而是点到大片大片的空白，一下子就把问题解决了。但是当地雷密度增高以后，在增大到一定程度以后，即使我们理性地分析，从不瞎猜，也不可能把扫雷问题做对了。
