17. 下列何者為屬於 NP-Complete 問題？
(A) Minimum Spanning Tree Problem
(B) Shortest Path Problem
(C) Subset Sum Problem
(D) Binary Search Problem

在計算複雜度理論中，NP-Complete (NPC) 問題是指那些在非決定性多項式時間內可以驗證解，且屬於 NP 類別中最困難的問題。如果能找到一個多項式時間演算法來解決任何一個 NP-Complete 問題，那麼所有的 NP 問題都可以在多項式時間內解決（即 P=NP）。

讓我們分析每個選項：

• (A) 最小生成樹問題 (Minimum Spanning Tree Problem)：

  • 這是一個可以在多項式時間內解決的問題。例如，使用 Prim 演算法或 Kruskal 演算法，其時間複雜度分別約為 O(E log V) 或 O(E + V log V)。因此，它屬於 P 問題。

• (B) 最短路徑問題 (Shortest Path Problem)：

  • 例如單源最短路徑（Dijkstra 演算法，O(E + V log V)）或所有配對最短路徑（Floyd-Warshall 演算法，O(V^3)）等問題都可以在多項式時間內解決。因此，它屬於 P 問題。

• (C) 子集和問題 (Subset Sum Problem)：

  • 給定一個整數集合和一個目標和，判斷是否存在一個非空子集，其元素之和等於目標和。這個問題是一個著名的 NP-Complete 問題。雖然存在一個在偽多項式時間內解決的動態規劃演算法（其時間複雜度與和的大小有關），但它並非真正意義上的多項式時間演算法（因為其複雜度依賴於輸入數值的大小，而非僅是輸入的位數）。

• (D) 二分搜尋問題 (Binary Search Problem)：

  • 這是一個在已排序的資料集中尋找特定元素的演算法，其時間複雜度為 O(log n)。這是一個非常高效的演算法。因此，它屬於 P 問題。

綜上所述，子集和問題是一個 NP-Complete 問題。