Một bài toán NP-đầy đủ dễ giải sẽ sụp đổ P và NP

Giả sử $B$ là NP-đầy đủ và có một thuật toán giải $B$ trong thời gian $O(n^{k_1})$. Lấy bất kỳ $A \in NP$; theo tính NP-đầy đủ của $B$, $A \le_p B$, nghĩa là tồn tại một hàm quy dẫn $f$ tính được trong thời gian $O(n^{k_2})$ biến các thể hiện của $A$ thành thể hiện của $B$ trong khi bảo toàn đáp án có/không.

Với một đầu vào $x$ độ dài $n$ của $A$, trước tiên tính $f(x)$: việc này mất thời gian $O(n^{k_2})$, và đặc biệt đầu ra $f(x)$ có độ dài nhiều nhất $O(n^{k_2})$ (một thuật toán thời gian đa thức không thể viết ra nhiều đầu ra hơn thời gian nó chạy). Sau đó chạy thuật toán thời gian đa thức cho $B$ trên $f(x)$: vì $|f(x)| = O(n^{k_2})$, việc này mất thời gian $O\big((n^{k_2})^{k_1}\big) = O(n^{k_1 k_2})$.

Tổng thời gian chạy là $O(n^{k_2}) + O(n^{k_1 k_2}) = O(n^{k_1 k_2})$, vẫn là một đa thức theo $n$ (hợp của hai đa thức là một đa thức). Theo tính đúng đắn của phép quy dẫn, $x$ là thể hiện có đáp án "có" của $A$ khi và chỉ khi $f(x)$ là thể hiện có đáp án "có" của $B$, nên thủ tục kết hợp này quyết định đúng $A$ trong thời gian đa thức.

Vì $A \in NP$ là bất kỳ, mọi bài toán NP đều có một thuật toán thời gian đa thức, tức $NP \subseteq P$. Kết hợp với bao hàm luôn đúng $P \subseteq NP$, ta có $P = NP$.