常見 NP 完全問題

命題分析

1) If $A \le_p B$, then $A$ is no harder than $B$

Verdict: True（對）

• 解釋： 因為能解 $B \implies$ 透過歸約就能解 $A$。

• $B$ 的解法邏輯上「包含」了 $A$ 的解法（加上一點多項式轉換的時間成本）。

2) If $A \le_p B$ and $B \le_p C$, then $A \le_p C$

Verdict: True（對）

• 解釋： 這是歸約的 傳遞性（Transitivity）。

• 先把 $A$ 轉成 $B$，再把 $B$ 轉成 $C$。兩個多項式時間的轉換合起來，總時間仍是多項式時間。

3) NP-Complete problems can be reduced to each other in polynomial time

Verdict: True（對）

• 解釋： 若 $X$ 與 $Y$ 都是 NP-Complete：

  1. $X$ 是 NP-hard，根據定義，這表示所有 $L \in NP$ 都可以歸約到 $X$ ($L \le_p X$)。

  2. 因為 $Y \in NP$，所以自然得出 $Y \le_p X$。

  3. 同理，因為 $X \in NP$ 且 $Y$ 是 NP-hard，所以 $X \le_p Y$。

• 結論： 它們彼此可以互相多項式歸約。

4) If $A \le_p B$ and $B$ is NPC, then $A$ is NPC too

Verdict: False（錯）

• 解釋： 方向不對。$A \le_p B$ 只表示 $B$ 的難度 $\ge A$，不能推出 $A$ 就一定很難（$A$ 可能很簡單）。

• 反例：

  • $A =$ 2-SAT（屬於 P，很容易解）

  • $B =$ 3-SAT（屬於 NP-Complete）

  • 確實存在 $2\text{-SAT} \le_p 3\text{-SAT}$（簡單問題當然可以歸約到難題），但這不會讓 2-SAT 變成 NP-Complete（除非 $P=NP$）。

5) If $A \le_p B$ and $A$ is NPC, then $B$ is NPC too

Verdict: False（錯）

• 解釋： 少了一個必要條件。

  • 由於 $A$ 是 NP-hard 且 $A \le_p B$，這確實意味著 $B$ 也是 NP-hard（這部分是對的，因為 $B$ 比 $A$ 難）。

  • 但要成為 NP-Complete (NPC)，還必須滿足條件：$B \in NP$。題目沒給這個前提，所以不能保證。

• 反例：

  • $A =$ SAT（NP-Complete）

  • $B =$ Halting Problem（停機問題，不可判定，甚至不在 NP 裡）

  • SAT 可以多項式歸約到 Halting Problem，但 Halting Problem 不是 NPC（因為它連 NP 都不是）。

• 補充： 如果題目修正為「若 $A$ 是 NPC 且 $A \le_p B$ 並且 $B \in NP$，則 $B$ 是 NPC」，那就會是 True。