子集合加總與分割（subset-sum and partition）

這裡有兩個聽起來很居家的數字謎題，其實偷偷是 NP 完全的。子集合加總（SUBSET-SUM）：給定一個正整數的多重集與目標 T，存在一個恰好加總為 T 的子集合嗎？（你能挑出其中一些鈔票，剛好湊成 100 元嗎？）分割（PARTITION）：你能把一個數的多重集切成兩組、使兩組總和「相等」嗎？（兩個人能否分一堆價格不同的物品，使各自付的總額相同？）兩者都感覺像算術而非圖論，這使它們成為「每當你要歸約到涉及數字或權重的東西時」的首選困難問題。

兩者都屬於 NP：憑證就是所選的子集合，而驗證器把選中的數加起來與目標比較——顯然是多項式。談困難性，關鍵事實是「分割是子集合加總的一個特例」：一個總和為 S 的多重集能被分成兩個相等的一半，恰好在它有一個加總為 S/2 的子集合時（剩下的那部分於是也加總為 S/2）。所以 partition <=p subset-sum 是顯然的。反方向的歸約 subset-sum <=p partition 是個漂亮的技巧：給定數字 a1, ..., an，目標 T，總和 S，加入兩個額外的數 S + T 與 2S - T（兩者皆正）。新的總和是 4S，所以相等分割需要每一側加總為 2S。那兩個大數不能同側（它們已經超過 2S），所以落在相反兩側；要平衡就逼得與 2S-T 同側的原始元素加總為 T（亦即與 S+T 同側的原始元素加總為 S-T）。因此新實例有相等分割，當且僅當原始實例有加總為 T 的子集合。為了把一切錨定，3-SAT <=p subset-sum 靠一個「位數裝置」歸約（每個變數貢獻一個數，在它自己的欄位、以及它所滿足的子句的欄位放 1；目標被選成讓各欄正確相加），證明子集合加總為 NP 完全；分割便繼承了它。

這兩個是證明「數值」問題困難的最愛種子——裝箱、兩機排程、背包可行性——因為它們的輸入是樸素的數字，其他算術問題能把它吸收進去。但這裡有一個關鍵的誠實，叫偽多項式陷阱。子集合加總「有」一個跑 O(n * T) 時間的動態規劃演算法，看起來是多項式。它不是：T 是一個用約 log T 位元寫成的數，所以它的輸入長度是 log T，而 O(n * T) 對那個長度而言是指數的——這叫「偽多項式」，只有在數字很小時才快。NP 完全性正好住在「數字很大」（很多位元）的實例裡，那裡 DP 表格寬到天文數字。所以子集合加總是個教科書教訓：「有一個看起來多項式的演算法」可能是一場由「不公平的（實質上一進位的）輸入規模視角」造出的海市蜃樓。