國中教甄｜資訊科技資訊科技112 年第 70 題單選題
Which one of the following descriptions of NP-Completeness is WRONG？
AAn NP-Complete problem is also an NP-Hard problem
BGiven an NP-Complete problem, the correctness of each solution can be verified in polynomial time.
CAn NP-Complete problem can be reducible to every problem in NP正確答案
DIf an NP-Complete problem can be solved in polynomial time, it implies P=NP
C正確答案
NP-Complete 問題的定義是 NP 中的所有問題皆可歸約至該問題，而非該問題可歸約至 NP 中的所有問題。
逐選項解析
AAn NP-Complete problem is also an NP-Hard problem✕ 錯誤
NP-Complete 問題必須同時滿足屬於 NP 且為 NP-Hard，因此 NPC 問題必定也是 NP-Hard 問題，敘述正確。
BGiven an NP-Complete problem, the correctness of each solution can be verified in polynomial time.✕ 錯誤
NP-Complete 問題屬於 NP 類別，而 NP 類別的定義即為其解的正確性可在多項式時間內被驗證，敘述正確。
CAn NP-Complete problem can be reducible to every problem in NP✓ 正確
DIf an NP-Complete problem can be solved in polynomial time, it implies P=NP✕ 錯誤
立即註冊,看完整詳解
這題的完整詳解,註冊就能看 · 每天 2 題免費
- 完整逐選項解析
- 秒殺解題技巧與破題關鍵
- 關鍵知識表整理
- 陷阱與易錯提醒
- 同考點歷屆題庫連續刷題與錯題本
