这次报告主要基于Richard kaye的论文“Minesweeper is NP-complete”，报告第一部分是介绍计算复杂度、NP完全性的基本概念，第二部分讨论了论文中的“minesweeper consistence problem”（MCP），并展示了richard kaye的将布尔可满足问题嵌入MCP以证明其NP完全性的方法。第三部分是对minesweeper的简短的延伸讨论,涉及 minesweeper的最优算法、概率计算的复杂度等问题。