# 转一个经典证明：扫雷是NP完全问题

Author posted @ 2011年8月11日 16:02 in Algorithm , 4308 阅读

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均无雷。

SEO 说:
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.

BSNL Customer Care n 说:
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.

HPBOSE Matric Questi 说:
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

anonymous 说:
2023年6月23日 04:41

anonymous 说:
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

anonymous 说:
2023年7月06日 06:42

You should mainly superior together with well-performing material, which means that see it: Bed Bug Treatment Oviedo

anonymous 说:
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

anonymous 说:
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

(输入验证码)
or Ctrl+Enter