1つのNP完全問題が易しければPとNPは崩壊する

$B$ がNP完全であり、$B$ を時間 $O(n^{k_1})$ で解くアルゴリズムがあるとする。任意の $A \in NP$ を取る；$B$ のNP完全性より $A \le_p B$ であり、これは $A$ のインスタンスを $B$ のインスタンスに写し、イエス/ノーの答えを保つ、時間 $O(n^{k_2})$ で計算可能な帰着関数 $f$ が存在することを意味する。

$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$ に関する多項式である（2つの多項式の合成は多項式である）。帰着の正しさより、$x$ が $A$ の「はい」インスタンスであることと $f(x)$ が $B$ の「はい」インスタンスであることは同値なので、この組み合わせた手続きは $A$ を多項式時間で正しく判定する。

$A \in NP$ は任意だったので、すべてのNP問題は多項式時間アルゴリズムを持つ、すなわち $NP \subseteq P$ である。常に成り立つ包含 $P \subseteq NP$ と合わせて、$P = NP$ が得られる。