第4章 多項式化約#

化約（reduction）是整個 NP 理論的樞紐：它讓我們能把「一個問題很難」的認識，從一個問題傳染到另一個問題。本章先建立化約的直觀概念與方向性，再根據化約定義 NP-hard 與 NP-complete，最後介紹 Cook-Levin 定理——它證明了 SAT 是第一個 NP-complete 問題，因此成為所有其他 NP-hard 證明的起點。