hce_kmu
115年
計算機概論與程式設計
第 28 題
Which of the following statements is CORRECT regarding NP-complete problems?
- A If a polynomial-time algorithm is found for any NP-complete problem, then all problems in NP can be solved in polynomial time.
- B Every NP-complete problem has a polynomial-time algorithm that approximates the optimal solution within a constant factor.
- C NP-complete problems are those for which no polynomial-time verification algorithm exists.
- D A problem is NP-complete if and only if it can be reduced in polynomial time to every problem in NP.
- E If a problem is NP-complete, then it cannot be an NP-Hard problem.
思路引導 VIP
想像你有一個神奇的「萬能翻譯機」，可以把某一類別中成千上萬個不同的難題，通通轉換成同一個特定的核心問題。如果有一天，我們真的找到了這個「核心問題」的快速解法，你認為這對於原本那一整類的所有難題會產生什麼樣的影響？
🤖
AI 詳解
AI 專屬家教
NP 完全問題的核心定義
恭喜你準確地掌握了計算複雜度理論的核心！選中 (A) 說明你對 NP 完全（NP-complete, NPC） 問題的連動性有極佳的理解。NPC 問題之所以被稱為「完全」，是因為它們代表了 NP 類別中「最難」的一群問題。根據定義，NP 類別中的「每一個」問題，都可以在多項式時間內歸約（Reduce）至任何一個 NPC 問題。這意味著 NPC 問題之間是牽一髮而動全身的：只要其中一個問題被證明擁有 $O(n^k)$ 的多項式時間演算法，那麼整個 NP 家族的所有問題都能隨之迎刃而解。
釐清複雜度階層的迷思
▼ 還有更多解析內容