# 證明 0–1 Integer Programming Problem 為 NP-Complete
## Exercises 34.5–2
Given an integer 𝑚 × 𝑛 matrix 𝐴 , and an integer 𝑚-vector 𝑏, the 0-1 integer-programming problem asks whether there exists an integer 𝑛-vector 𝑥 with elements in the set {0, 1} such that 𝐴𝑥 ≤ 𝑏. Prove that 0-1 integer programming problem is NP-complete (Hint: Reduce from 3-CNF-SAT.)

問題：是否存在一大小為 n 的 vector 𝑥（𝑥 中的元素皆為0或1）使得 𝐴𝑥 ≤ 𝑏 ？

1. 證明 0-1 IP ∈ NP
給定一大小為 n 的 vector 𝑥（𝑥 中的元素皆為0或1），欲驗證 𝐴𝑥 ≤ 𝑏 是否成立，只需將 𝐴𝑥 相乘，並將結果與 𝑏 一一比對。時間複雜度為 O(mn) + O(m)，可於 polynomial time 完成。
2. 證明 3-CNF-SAT ≤~p~ 0-1-IP

把3-CNF-SAT問題轉換為0-1-IP問題:
- 假設 Φ 有 m clauses 和 n variables。
- 我們可以把每個 clause (𝑥~1~ ∨ ¬𝑥~2~ ∨ ¬𝑥~3~) 轉換成不等式 𝑥~1~ + (1 - 𝑥~2~) + (1 - 𝑥~3~) ≥ 1，再整理為 - 𝑥~1~ + 𝑥~2~ + 𝑥~3~ ≤ 1。
- 透過觀察可發現，沒有做 not 運算的 variable 會乘上 -1，有經過 not 運算的 variable 則乘上 1。
- 而不等式右邊的值，則為 not 的數量 - 1。
- 得出矩陣 𝐴 的轉換 Function:

$$a_{i,j} = \left\{
\begin{aligned}
-1 & & if \ x_j ∈ C_i\\
1 & & if \ ¬x_j ∈ C_i\\
0 & & otherwise
\end{aligned}
\right.$$

- 而 vector 𝑏 的轉換為:

$$b_i = \sum\limits_{j = 1}^n{max(0, a_{i,j}) - 1}$$

證明存在一個n-vector 𝑥: 𝐴𝑥 ≤ 𝑏 ⟺ Φ。
轉換的時間複雜度為O(mn)，可於 polynomial time 完成。

由 1. 和 2. 可得知：可以將 3-CNF-SAT 問題 reduce 到 0-1 Integer-Programming 問題，0-1 Integer-Programming 問題為NP-Complete 問題。

Example:
Φ = (𝑥~1~ ∨ 𝑥~2~ ∨ ¬𝑥~3~) ∧ (𝑥~1~ ∨ 𝑥~3~ ∨ 𝑥~4~) ∧ (¬𝑥~2~ ∨ ¬𝑥~3~ ∨ ¬𝑥~4~)

$$
\left[
\begin{array}{cccc}
-1 & -1 & 1 & 0 \\
-1 & 0 & -1 & -1 \\
0 & 1 & 1 & 1
\end{array}
\right] ×
\left[
\begin{array}{cccc}
x_1 \\
x_2 \\
x_3 \\
x_4
\end{array}
\right] ≤
\left[
\begin{array}{cccc}
0 & -1 & 2
\end{array}
\right]
$$

> [name=什麼] 當初寫這題的時候看得很痛苦所以試圖造福後人ㄉ我，希望可以幫上忙ㄛ

---

參考資料：[Proving 0-1 integer programming is NP-complete (using reduction from 3-CNF-SAT)](https://gnarlyware.com/blog/proving-0-1-integer-programming-is-np-complete-using-reduction-from-3-cnf-sat/)