一个NP完全问题若易解则P与NP塌缩

设 $B$ 是NP完全的，且存在一个在时间 $O(n^{k_1})$ 内求解 $B$ 的算法。任取 $A \in NP$；由 $B$ 的NP完全性可知 $A \le_p B$，即存在一个在时间 $O(n^{k_2})$ 内可计算的归约函数 $f$，把 $A$ 的实例映射为 $B$ 的实例，同时保持是/否答案不变。

对 $A$ 的一个长度为 $n$ 的输入 $x$，先计算 $f(x)$：这需要时间 $O(n^{k_2})$，特别地输出 $f(x)$ 的长度至多为 $O(n^{k_2})$（多项式时间算法写出的输出不能比其运行时间更长）。然后在 $f(x)$ 上运行求解 $B$ 的多项式时间算法：由于 $|f(x)| = O(n^{k_2})$，这需要时间 $O\big((n^{k_2})^{k_1}\big) = O(n^{k_1 k_2})$。

总运行时间为 $O(n^{k_2}) + O(n^{k_1 k_2}) = O(n^{k_1 k_2})$，仍是关于 $n$ 的多项式（两个多项式的复合仍是多项式）。由归约的正确性，$x$ 是 $A$ 的「是」实例当且仅当 $f(x)$ 是 $B$ 的「是」实例，因此这一组合过程能在多项式时间内正确判定 $A$。

由于 $A \in NP$ 是任意的，每个NP问题都有多项式时间算法，即 $NP \subseteq P$。结合恒成立的包含关系 $P \subseteq NP$，即得 $P = NP$。