Partition Problem is NPC

題目

Proof

(1)Partion Problem (PP)

$\in$ NP
給定一組 PP 的 Yes-instance

$(A,S-A)$，則我們可以在多項式時間內檢查 (1) A 和 S-A 的元素總和相同 (2) A 和 S-A 互斥，即

$S\cap (S-A)=\mathrm{\varnothing }$
所以

$PP\in NP$

(2) Partion Problem

$\in$ NP-Hard
目標 :

$SUBSETSUM{\le }_{p}PARTITION$
SUBSET-SUM : 給定一整數集合 S 和目標整數 W，是否存在一子集合

$S^{\prime }\subseteq S$ 使得所有元素總和為 W。

給定一組 SUBSET-SUM 問題 (SSP) 的 Instance (S, W)，可由以下方式建構 PARTITION 問題的 Instance : 令 T 為所有 S 中的元素總和，將 PARTITION 的 Instance 設為

$S^{\ast }=S\cup \{|T-2W|\}$。

假設 SUBSET-SUM 的答案是 YES，即存在一子集合

$S^{\prime }\subseteq S$ 使得所有元素總和為 W，則

$S-S^{\prime }$ 的所有元素總和必為 T - W。而將這兩個集合 S 和 S - S' 的總和相減，再取絕對值為 |T - 2W|，這就是這兩個集合的總和差距。因此只要將 |T - 2W| 加入總和較小的集合中就可以得到兩個總和相等的集合了，也就是說

$S^{\ast }$ 可以找到一分割方式使得兩個集合總和相等，PARTITION 的答案也會回傳 YES。

相反地，假設 PARTITION 的答案是 YES，即

$S^{\ast }$ 存在一種分割方式使得兩個集合總和相等，總和為

$\frac{T+|T-2W|}{2}$。

• 若
  $T\le 2W$，兩集合總和皆為
  $\frac{T+2W-T}{2}=W$，此時 S' 就選擇沒有包含元素 |T - 2W| 的集合即為 SUBSET-SUM 的答案。
• 若
  $T>2W$，兩集合總和皆為
  $\frac{T+T-2W}{2}=T-W$，此時選擇包含元素 |T - 2W| 的集合，並把元素 |T - 2W| 去除後得到一個集合 S' 使得總和變成 (T - W) - (T - 2W) = W，則找到一個集合 S' 使得總和為 W，可得 SUBSET-SUM 的答案為 YES。

由 (1)(2) 可得 Partition Problem

$\in$ NPC