歸約小元件（reduction gadget）

當你把一個問題歸約到另一個時，你是在翻譯，而小元件就是這份翻譯裡可重複使用的片語：目標結構中一小塊自成一體的部件，用來模擬來源的某一個特徵。把它想成用標準零件組裝裝置：一個零件代表一個變數、另一個代表一個子句，你把它們扣在一起。小元件就是 NP 困難證明的樂高積木。

具體地說，一個典型的從 3-SAT 到某圖問題的歸約用兩種小元件。「變數」小元件是一張小子圖，有兩種穩定的構型，一種讀作「真」、一種讀作「假」，於是選擇構型就模擬了設定變數。「子句」小元件是一張子圖，它能被完成（著色、覆蓋、走過）當且僅當其文字中至少一個被設為真。你為公式的每個變數與每個子句各建一份對應的小元件，再用連接邊把它們接起來，使得目標問題的合法解存在，恰恰當存在一個滿足賦值時。整個構造必須能在多項式時間內完成，且只產生多項式大小的輸出。

小元件歸約的藝術，在於讓局部的零件強制出你要的整體行為，不許作弊。兩條正確性義務必須同時成立：每個滿足賦值都產生目標的一個合法解（完備性），且目標的每個合法解都編碼一個滿足賦值（健全性）。只得到一個方向而沒有另一個，歸約就錯了。經典的小元件構造——3-SAT 到團、到頂點覆蓋、到三著色、到漢米頓迴路——值得研讀，不是為了背它們，而是因為它們教你如何把一個問題的規則逼成另一個問題的規則。