结果于 2000 年发表在Mathematical Intelligencer上,论文题目是 Minesweeper is NP-complete ,这里有作者的简单的问题和证明介绍.证明方法是证明扫雷问题可以编码任何逻辑电路,包括 NP-hard 的 3SAT 问题.作者还有一个非常直观的 PPT演示证明过程,比如下图展示如何编码 AND 逻辑门:$ t=u\wedge v$
它是 NP 完全问题说明如果程序要想完全正确,所费的时间最坏情况下将是指数的.不过我猜测对于大部分的扫雷的实例还是很容易的,而且 NPC 所用的规约实例特别大,所以编一个能较快速度解决大部分 windows 自带的那个高级难度的扫雷问题还是可行的,不知道是否已经有这方面的程序.
很多人一看到 NP-hard ,就从字面上理解成为比 NP 还难的问题.但如果这里的"更难"指得是解决问题所花费时间更长的话,这个论断是不正确的.从算法角度来看, NP-hard 问题的确比 NP 难,但比 NP 还难(指花费时间更多)的问题却不见得是 NP-hard 的.
更新:证明的关键一步发现错误,作者更新了论文,结论甚至论文标题都改了(废话),新版本On the graph isomorphism problem.
Game Theory 即博弈论,目前在经济学中运用得最多(纳什更因为他在这上面的工作拿到了诺贝尔经济学奖).但在最近几年,理论计算机界对它的研究也很热.
素数筛法的复杂度 相似度: 0.063
Xie Xie 给我看了一个链接性能调优--永远超乎想象,里面提到了素数筛法的复杂度,作者用实验发现此筛法是线形的.