算法設計大作業 8章第3題

題目

STINGY SAT is the following problem: given a set of clauses (each a disjunction of literals) and an integer k, find a satisfying assignment in which at most k variables are true, if such an assignment exists. Prove that STINGY SAT is NP-complete

大意：

定義一個STINGY SAT問題：給定一組子句（由文字通過邏輯或連接配接起來）和一個整數k，是否存在一個真值指派使得最多隻有k個變量為真。證明這個問題是NP完全問題。

證明：

1. 首先說明一下SAT，SAT又叫可滿足性問題，描述的是給定一個合取範式（CNF），要麼給出它的一個真值指派，要麼報告它不存在真值指派。
2. 另外，給定一組解{x1, x2, …, xn}，我們是可以在多項式時間内驗證其正确性的，是以STINGY SAT屬于NP問題。

3. 接下來我們把SAT規約到STINGY SAT： 

   i) SAT是STINGY SAT的一個特例，假設SAT的函數為f，給定n個變量x1, x2, …, xn，最多有n個變量為真，那麼(f, n)可以看成是STINGY SAT的執行個體。 

   ii) 假設STINGY SAT的執行個體是(f, n)，那麼(f, n)的一個真值指派，也一定是SAT函數f的一個真值指派，即f是SAT的執行個體

       以上可把SAT規約到STINGY SAT，由于SAT是NP完全問題，是以STINGY SAT也是NP完全問題。