转一个经典证明：扫雷是NP完全问题
曾经看到过自动扫雷软件，当时我就在想，扫雷游戏是否有什么牛B的多项式算法。最近才看到，扫雷问题居然是一个NP完全问题，并且这个定理有一个简单、直观而又神奇的证明。在这里和大家分享一下整个证明过程。
首先，扫雷一定是NP问题，它显然可以在多项式的时间里验证一个解。接下来，我们需要把一个已知的NP完全问题归约到扫雷问题上去。我们将给出一种把逻辑电路问题归约到扫雷问题的方法，这样的话我们就可以利用扫雷问题解决逻辑电路问题，从而说明逻辑电路问题不比扫雷难。我们将把逻辑电路问题转换成一种对应的扫雷布局，就像画画一样把逻辑电路画在扫雷的棋盘上。如果你还不知道什么叫NP完全问题，什么叫逻辑电路问题，你可以看一看我的这篇文章。
上图就是一条带有Boolean值的线路。注意到x和x'中有且仅有一个有雷。如果（沿线路方向）前一个格子有雷，我们就说这条线路状态为True；反之如果后一个格子有雷，那么这条线路所传递的Boolean值就是False。每条线路的起始端都如下图左所示，其中符号*表示该格里必然有雷，x和x'中同样是有且仅有一个有雷，但到底是哪一个里面有雷谁也说不清楚。线路是可以拐弯的，如下图右所示，这可以保证转角后Boolean值相同。
我们需要构造一些特殊的扫雷布局来解释NOT门、AND门和OR门。构造NOT门最为简单，下图就是一个NOT门，注意经过了中间的NOT门后，x和x'的位置互换，True变成了False，False也将变成True。
AND门和OR门的构造就比较复杂了。下面是AND门的构造，U和V是输入的两条线路，T是输出的线路。为了说明这确实是一个AND门，我们将说明：在下面的构造中，如果线路T是True（即最右边那个格子t有雷）的话，那么格子u和v必须都有雷才行。如果最右边的格子t有雷，我们可以很快推断出，图中所有其它的t格都是有雷的，所有t'都是无雷的。观察a3正上方的那个"3"，我们立即看出a2,a3都必须有雷，于是继续推得a1无雷，s有雷。类似地，我们可以知道r也是有雷的。在中间一行的*4t处，4的上下左右都已经有雷了，那么u'和v'必然无雷，于是继续往左推得u和v都有雷。
OR门的构造比较类似，如下图。如果r无雷的话，可知a2,a3有雷，a1无雷，s'有雷，进而s无雷。观察"6"可知u'和v'都有雷，于是u和v均无雷。
不断套用这几个逻辑门的构造图来连接电路，直到输出线路只剩下唯一的一条。把最后的输出线路从x或者x'处截断（相当于把最终输出的Boolean值定下来）后，整个布局就成了一个“扫雷版SAT问题”了。
最后还有一个容易忽略的问题：要是线路交叉了该咋办？下图的构造可以保证线路交叉后仍不改变原线路所带的Boolean值。至此，我们已经可以把任一逻辑电路布局到扫雷棋盘上，解决这个扫雷问题就相当于要解一个逻辑电路问题，因此扫雷问题至少和逻辑电路问题一样难。
2022年3月17日 00:34
Any of you interested in hung doors? I have seen from forums that Caldwells sell such doors from high quality materials at the lowest price. https://caldwells.com/interior-doors/glass-doors's the link to their site.
2022年8月08日 15:20
The new digital era based support system contributing a lion’s sharing related to all telecom services in 2021 calendar year, also find the new email address providing BSNL complaint process for payment failed issues for any digital payment service failure related issues like repayment, The new digital era based support system contributing a lion’s sharing related to all telecom services in 2021 calendar year, BSNL Customer Care number refund of debited amount and service activation /deactivation, complaints, tariff change requests.
2022年9月05日 21:25
HPBOSE 12th Model Paper 2023 will help the Students to get a Clear idea about the Exam 2023. old Exam Paper is provided by the HPBOSE official website. Students can Download the Haryana 10th Last Year Exam Question Paper HPBOSE Matric Question Paper as Pdf format from this page. Therefore, Students here we are providing HP 12th Sample Paper 2023 for Hindi, English to make you familiar with new Syllabus for upcoming Final exam 2023
2023年6月23日 04:41
There you can download for free, see the first of these data. Kissimmee Termite Control
2023年7月06日 06:40
This is very interesting content! I have thoroughly enjoyed reading your points and have come to the conclusion that you are right about many of them. You are great. Bed Bug Treatment Orlando
2023年7月06日 06:42
You should mainly superior together with well-performing material, which means that see it: Bed Bug Treatment Oviedo
2023年9月10日 16:35
Awesome dispatch! I am indeed getting apt to over this info, is truly neighborly my buddy. Likewise fantastic blog here among many of the costly info you acquire. Reserve up the beneficial process you are doing here. Tax Accountant
2023年9月11日 22:59
Thanks for writing such a good article, I stumbled onto your blog and read a few post. I like your style of writing... Information Security