題組內容

四、電腦可用來解決許多問題：（每小題 5 分，共 25 分）

⑶有些問題被稱為 NP-complete，何謂 NP-complete？

詳解 (共 1 筆)

詳解提供者：白龍@菜鳥公務員(107/10/29)

NP完全或NP完備（NP-Complete，NP-C或NPC）:

是計算複雜度理論中，決定性問題的等級之一。NPC問題，是NP（非決定性多項式時間）中最難的決定性問題。因此NP完備問題應該是最不可能被化簡為P（多項式時間可決定）的決定性問題的集合。若任何NPC問題得到多項式時間的解法，那此解法就可應用在所有NP問題上。

經典NPC問題: