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) = \emptyset$
所以 $PP \in NP$

(2) Partion Problem $\in$ NP-Hard
目標 : $SUBSET\ SUM\ {\le}_p\ PARTITION$
SUBSET-SUM : 給定一整數集合 S 和目標整數 W，是否存在一子集合 $S' \subseteq S$ 使得所有元素總和為 W。

給定一組 SUBSET-SUM 問題 (SSP) 的 Instance (S, W)，可由以下方式建構 PARTITION 問題的 Instance : 令 T 為所有 S 中的元素總和，將 PARTITION 的 Instance 設為 $S^* = S \cup \{|T-2W|\}$。

假設 SUBSET-SUM 的答案是 YES，即存在一子集合 $S' \subseteq S$ 使得所有元素總和為 W，則 $S - S'$ 的所有元素總和必為 T - W。而將這兩個集合 S 和 S - S' 的總和相減，再取絕對值為 |T - 2W|，這就是這兩個集合的總和差距。因此只要將 |T - 2W| 加入總和較小的集合中就可以得到兩個總和相等的集合了，也就是說 $S^*$ 可以找到一分割方式使得兩個集合總和相等，PARTITION 的答案也會回傳 YES。

相反地，假設 PARTITION 的答案是 YES，即 $S^*$ 存在一種分割方式使得兩個集合總和相等，總和為 $\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