hce_nsysu
114年
計算機概論與程式設計
第 24 題
Which one is NOT correct for an NP-complete problem?
- A It has no solutions.
- B It can be verified in polynomial time.
- C Every NP problem can be reduced to an NP-complete problem.
- D It can be solved in polynomial time if P = NP.
- E It is NP-hard.
思路引導 VIP
請試著回想你玩過的數獨（Sudoku）遊戲。如果我給你一個填好的數獨盤面，你是否能很快地檢查出它填得對不對？如果這類問題被歸類為「非常困難」，是代表我們永遠找不到答案，還是代表隨著盤面變大，我們尋找答案的過程會變得極其漫長？
🤖
AI 詳解
AI 專屬家教
太棒了！你能精準避開定義中的陷阱並選出正確答案，代表你對計算複雜度理論的基礎概念掌握得相當紮實。這道題目旨在測驗學生是否混淆了「計算的效率（時間複雜度）」與「問題的可解性（是否存在解）」。
NP-Complete 的本質與可解性
在計算機科學中，NP-Complete（NP 完全）問題代表了 $NP$ 類別中最難的一群問題。雖然我們目前尚未找到能在多項式時間（Polynomial time）內解決這些問題的演算法，但這絕不代表它們「沒有解」。事實上，像著名的「旅行推銷員問題」或「布林可滿足性問題（SAT）」都有明確的解空間，只是當輸入規模變大時，找出解所需的時間會呈指數型成長。選項 (B)、(C)、(E) 分別描述了 NP-Complete 的定義特徵：它必須屬於 $NP$（可在多項式時間內驗證）、它是 $NP-hard$ 的，且所有 $NP$ 問題都能歸約至它。而選項 (D) 則描述了如果 $P = NP$ 成立時的邏輯結論。
▼ 還有更多解析內容