Algorithm - Ch6 NP-完全問題 NP-Completeness

Chapter 6   NP-Completeness

6.1   P、NP、NP-Hard、NP-Complete

• P、NP、NP-Hard、NP-Complete這些概念都是用來描述一個問題的難度。也就是一個問題能否在以上時間內求解，或者驗證一個解是否符合一個問題。
• P：用deterministic演算法在polynomial time可以decided
• NP：用non-deterministic演算法在polynomial time可以decided
           (也就是polynomial-time verifiable)
• NP-Hard：所有NP皆可polynomial-reduce至NP-Hard
• NPC：
• NPC ∈ NP
• 所有NP皆可polynomial-reduce至NPC (NPC ∈ NP-Hard)

• P = NP ?
• Computer science 最經典的一個問題。實際上，就是說找到一個問題的解的難度，和驗證一個解是否滿足某個問題的難度相同嗎？主流認為P是NP的子集，但目前依然是一個無解的開放問題。 

• NP-Completeness
• NP-Completeness：NP問題中的代表問題，例如 satisfiability 
• SAT = { 空  |  是一個可滿足的布林公式 }，對一個確定的邏輯電路，是否存在一種輸入使輸出為true，是第一個被證明的NPC問題
• Cook-Levin theorem：只要證明SAT在P裏面 , P就是NP
• NP-Completeness證明法 (證明Q為NPC)
• Q屬於NP
• 某個NPC Q’可polynomial-time reduce至Q (NPC形成一個equivalence class)

6.2   Reducibility

• 遇到一個問題，通常我們思考的是如何解它，使用像是divide-and-conquer、dynamic programming等算法，但如果怎樣也想不到高效的算法怎麼辦？我們可以把目前的問題通過”Reduce”的方式，變成一些「困難已知問題」的子問題，這樣就能證明這個問題這個世界上的天才都沒能找到高效的算法。
• A可以reduce為B：問題B的答案可用於解決問題A，因此解決A不會難於解決B
•   B is decidable  —>A is decidable
• A is undecidable —>B is undecidable
• 寫作 A ≦ B，通常也在≦符號下標使用的歸約手法。

• 3SAT轉CLIQUE

• 3SAT轉VERTEX-COVER

• 3SAT轉HAM-PATH