魔塔问题属于NPC的证明
通过证明：0-1背包问题可归约到标准魔塔问题，得出判定问题——标准魔塔问题是NPC的
标准魔塔问题的定义
通俗的讲，标准魔塔问题是魔塔的简化，只考虑生命、攻击、防御、红蓝宝石，数值无上限；不考虑钥匙、金币、商店、道具等。
严格定义
给定一张$w\times h$的网格地图，地图上有墙与平地，同时给定玩家起点与终点坐标。给定玩家的初始属性：生命($HP$)、攻击($OFS$)、防御($DFS$)。地图的平地上一共有$n$个物件，它们可以是以下之一：
- 红宝石：玩家移动到该位置时可增加$X_i$点攻击，获得后该位置变为平地；
- 蓝宝石：玩家移动到该位置是可增加$Y_i$点防御，获得后该位置变为平地；
- 怪物：第$i$个怪物具有生命值$h_i$，攻击$o_i$，防御$d_i$. 与怪物战斗会损失$damage$点生命，只有生命值严格大于$damage$时才可击败通过，击败后该位置变为平地，$damage$的计算方法见后文。
所有的数值均为非负整数，且没有上限。
问：玩家可以成功走到终点吗？
damage计算方法
设玩家此时的生命，攻击，防御分别为$h_p$,$o_p$,$d_p$；对应怪物的生命，攻击，防御分别为$h_i$,$o_i$,$d_i$，则$damage=f(o_p,d_p,h_i,o_i,d_i)$.
$$
f(o_p,d_p,h_i,o_i,d_i) = \begin{cases}
+\infty&, o_p\leq d_i \\
0& ,o_p>d_i \mbox{且} o_i\leq d_p \\
\lfloor\frac{h_p-1}{o_p-d_i}\rfloor\times(o_i-d_p)& ,Otherwise
\end{cases}
$$
上面公式的解释：通俗来讲玩家每回合攻击怪物$o_p-d_i$点生命，怪物每回合攻击玩家$o_i-d_p$点生命。玩家先行动，如此循环直到某一方生命减为0或更低。
任何魔塔问题都是NP
证据$t$即为攻略，攻略至多$O(n)$个步骤，只需逐步模拟即可验证魔塔是否可通关。
标准魔塔问题不比0-1背包问题简单
归约
对于一个0-1背包问题的实例：重量${w_1,\cdots,w_n}$，价值${v_1,\cdots,v_n}$. 容量$L$，问其价值可以达到$V$吗？
设$S_v=\sum v_i$，用如下方法构造标准魔塔问题：
初始状态：玩家生命为$L+1$，攻击$S_v$，防御$0$.
地图有一个主路，可以直接达到终点，但被一个生命$1$，攻击$1$，防御$S_v+V-1$的怪物$M_0$守住门口。
有$n$个支路，第$i$条支路有一个可增加$v_i$点攻击的红宝石，但被一个生命$2S_V$，攻击$w_i$，防御$0$的怪物$M_i$守住路口。
这是一个多项式时间变换，如果这个标准魔塔问题有解，则0-1背包输出“Yes”，否则输出”No”.
正确性证明
有以下明显的事实：
- 当且仅当玩家通过吃宝石增加共计$V$点攻击后，才可击败$M_0$，且玩家不会受到伤害；
- 玩家在地图中的攻击不小于$S_v$，且若有支路怪存活，攻击严格小于$2S_v$。这意味着，只要有支路怪存活，支路怪均恰好攻击玩家一次，即对玩家造成$w_i$点伤害。
因此，没击败一个支路怪$M_i$获得对应宝石，即等价于将第$i$件物品放入背包；背包容量为$L$，等效于玩家生命始终为正。一旦获得到了$V$点攻击（即价值达到$V$），则可无损伤地击败$M_0$通关。
由此证明了：0-1背包问题$\leq_p$标准魔塔问题。
有商店的魔塔问题
事实上，红宝石增加能力值永远为常数的情形，上述方法会失效；以常数1为例，即便可以通过$v_i$个宝石以等效实现增加$v_i$点能力，但这已经不是多项式时间变换。注：如果魔塔中有增加$1,2,4,\cdots$点数值的不同宝石，则$\log v_i$个宝石即可等效，依然是多项式时间变换。
但注意到，几乎所有的魔塔都拥有金币-商店系统，下面指出：有商店的魔塔问题不比0-1背包问题简单。
事实上此结论trivial，仿照标准魔塔问题的归约方案，去掉所有的宝石，改为击败怪物$M_i$可获得$v_i$点金币；还有一个商店，$V$点金币可以增加$V$点攻击，这依然是多项式时间变换。
有机关门的魔塔问题
一旦引入机关门，便容易证明3-SAT$\leq_p$有机关门的魔塔问题，细节从略。
结论
由于0-1背包问题和3-SAT问题都是已知的NPC，因此：
- 标准魔塔问题是NPC
- 有商店的魔塔问题是NPC
- 有机关门的魔塔问题是NPC
事实上，以上三种问题往往是某个实际魔塔问题的特殊情况（子问题），如果算法A能够求解出某个实际魔塔的通关路线，则算法A也能解决以上三个问题之一（通常是有商店的魔塔问题），由此可以得到推论：
目前，人类没有找到可以求解实际魔塔问题通关路线的多项式时间算法，且目前普遍认为不存在多项式时间算法。对于一个魔塔求解器而言，利用回溯与分支限界的算法应该是高性价比的算法之一。