经典证明：星际争霸是NP-hard的

今天看到这里(http://arxiv.org/pdf/1201.4995v1.pdf)给出了一个“星际争霸是 NP-hard 问题”的一个证明。具体地说，给定一个初始布局（包括地图、双方已有资源、双方已有建筑、双方已有兵力），判断其中一方是否能获胜，这个问题是 NP-hard 的。当然，考虑到即时战略游戏的复杂性，这个结论并不出人意料；真正有趣的，则是如何巧妙地利用游戏中的元素，构造出极其精巧的初始局面，从而转化成某个已知的 NP-complete 问题。下面是原文中给出的证明。这个证明有没有什么漏洞？你还能想到哪些别的证明方法？欢迎在下面留言一同分享。

假设初始时有 A 、 B 两位玩家，他们分别位于两个孤岛上。玩家 B 有非常多的地面兵力，但没有空中单位，并且已有资源为 0 ，而且还没有任何经济来源。他只能坐等玩家 A 来攻打他。玩家 A 一开始则完全没有兵力，但他有不少可以生产作战单位的建筑，也有一定的经济来源，理论上有获胜的希望。地图上还有第三个孤岛，孤岛周边放满 B 的对空防御，玩家 A 即使派遣空中部队也无法进入该孤岛。

初始时，玩家 A 的资源刚好够造一个农民，玩家 A 还需要收集额外的 x 个单位的资源才足以消灭玩家 B 。但是，玩家 A 的所有可采集资源都在第三个孤岛上。这个孤岛上有 n 个采矿点，每个采矿点都配备有一个基地，以及 x/n 个单位的矿石资源。每个采矿点也都还预先配备了一个农民，只不过这个农民被矿石围在里面出不来了。采矿点与采矿点之间靠一些小路连接，每条路上都有玩家 B 的防御塔，保证一个农民走过去必死无疑，但是两个农民走过去恰好能活一个。

游戏开始后，玩家 A 唯一获胜的途径便是，在某个采矿点建造一个农民，采完这个采矿点的矿，把被困的农民救出来，然后选择某条小路走到下一个采矿点（途中死掉一个农民），继续采矿并解救农民，以此类推，直到走遍每一个采矿点，采完所有的矿。很容易看到，玩家 A 相当于要解决一个 Hamilton 路的问题（注意，即使平面图的 Hamilton 路问题也是 NP-complete 的）。因此，星际争霸是 NP-hard 的。