55. 在計算複雜度理論中，請問下面哪一個敘述為非？
(A) NP 問題是指無法在多項式時間內可以找出解的決定性問題
(B)所有 NP 問題都可以在多項式時間內被歸約（reduce to）為 NP 完備（NP-Complete）問題
(C)背包問題是一個 NP 完備（NP-Complete）問題
(D) NP 完備（NP-Complete）是 NP 與 NP 困難（NPHard）問題的交集

好的，我們來分析計算複雜度理論中的這些敘述，找出不正確的一個。

計算複雜度理論 (Computational Complexity Theory) 基礎概念：

• P 問題 (Polynomial time)：

  • 可以在多項式時間內被解決的決定性問題。
  • 「多項式時間」是指演算法的執行時間 T(n) 可以被一個多項式函數 nk (其中 k 是常數) 所限制，即 T(n)=O(nk)。

• NP 問題 (Nondeterministic Polynomial time)：

  • 無法在多項式時間內被解決，但可以在多項式時間內驗證一個給定的解是否正確的決定性問題。
  • 「非決定性」指的是演算法可以在每一個步驟中「猜測」一個正確的選擇，最終在多項式時間內找到解。實際的電腦是「決定性」的，所以「非決定性多項式時間」意味著如果有一個「神諭」來引導我們做正確的猜測，我們可以在多項式時間內找到解。

• NP 困難問題 (NP-Hard)：

  • 如果所有的 NP 問題都可以在多項式時間內歸約 (reduce) 到某個問題 L，那麼問題 L 就是 NP 困難問題。
  • NP 困難問題不一定是 NP 問題（即它可能不是決定性問題，或者即使是決定性問題，也可能無法在多項式時間內驗證解）。
  • 簡單來說，NP-Hard 問題至少和最難的 NP 問題一樣難，甚至可能更難。

• NP 完備問題 (NP-Complete, NPC)：

  • 同時滿足以下兩個條件的問題：
    1. 它是一個 NP 問題。
    2. 它是一個 NP 困難問題。
  • 換句話說，所有的 NP 問題都可以在多項式時間內歸約到 NP 完備問題。如果能找到一個多項式時間演算法來解決任何一個 NP 完備問題，那麼所有的 NP 問題都可以在多項式時間內解決（這就是著名的 P vs NP 問題的核心）。

現在我們來逐一分析選項：

(A) NP 問題是指無法在多項式時間內可以找出解的決定性問題

• 分析： 這個敘述是不精確的，甚至是錯誤的。NP 問題的定義是可以在多項式時間內驗證解的決定性問題。它不一定是無法在多項式時間內找出解，因為所有 P 問題也都是 NP 問題（P 是 NP 的子集，如果 P=NP 則所有 NP 問題都可以在多項式時間內解決）。所以，說「無法在多項式時間內找出解」是不準確的，因為我們不知道 P 是否等於 NP。
• 判斷： 這個敘述有誤。

(B) 所有 NP 問題都可以在多項式時間內被歸約（reduce to）為 NP 完備（NP-Complete）問題

• 分析： 這是 NP 完備問題的定義之一。一個問題 L 是 NP 完備的，如果所有 NP 問題都可以多項式時間歸約到 L。這意味著如果能解決一個 NP 完備問題，就能解決所有 NP 問題。
• 判斷： 這個敘述是正確的。

(C) 背包問題是一個 NP 完備（NP-Complete）問題

• 分析： 背包問題 (Knapsack Problem) 的決策版本（即判斷是否存在一個子集總和等於 K）是經典的 NP 完備問題。
• 判斷： 這個敘述是正確的。

(D) NP 完備（NP-Complete）是 NP 與 NP 困難（NP-Hard）問題的交集

• 分析： 正如上面定義的，一個問題是 NP 完備的，當且僅當它既是 NP 問題，又是 NP 困難問題。這表示 NP 完備問題集合就是 NP 集合和 NP 困難集合的交集。
• 判斷： 這個敘述是正確的。

最終判斷：

最不正確的敘述是 (A)，因為它對 NP 問題的定義有誤，且暗示了 P 不等於 NP，而 P vs NP 至今仍是未解之謎。NP 問題的正確定義是「其解可以在多項式時間內被驗證」。

The final answer is A​