NP-完全性介绍
【0】README
0.1） 本文總結于 數據結構與算法分析， 旨在 理解 “NP-完全性” 的idea ；
【1】難與易
1.1）不可判定問題：正如實數不足以表示 x^2 < 0 的解那樣，可以證明， 計算機不可能解決碰巧發生的每一個問題，這些不可能解出的問題叫做不可判定問題；
1.2）停機問題：一個特殊的不可判定問題是 停機問題——是否能夠讓你的C 編譯器擁有一個附加的特性，即不僅能夠檢查語法錯誤，而且還能夠檢查所有的無線循環？
1.3）遞歸不可判定問題：上述問題之所以是不可判定問題的原因在于， 這樣一個程序可能很難檢查它自己， 由于這個原因， 有時這些問題叫做是 遞歸不可判定的；
【2】NP類問題
2.0）網絡轉載：
- 2.0.1）P類問題定義： 如果一個問題可以找到一個能在多項式的時間里解決它的算法，那么該問題就是P類問題；
- 2.0.2）NP問題定義：指可以在多項式的時間里驗證一個解的問題， 也可以說：可以在多項式的時間里， 猜出解的問題；（通常，我們找一個解很困難，但是驗證一個解卻很容易， 驗證一個解只需要花費O（n）的時間復雜度， 也就是說我們可以花 O（n）的時間吧我猜的路徑長度加起來）；
- 2.0.2.1）為什么要定義NP問題？ 是因為通常只有NP問題才能找到多項式的時間可以解決的算法， 所以P類問題屬于NP類問題；
- 2.0.2.2）人們普遍認為 P≠NP類問題： 就是因為在研究NP問題的過程中 找出一類非常特殊的NP問題——NPC類問題（NP完全問題）；
- 2.0.3）NPC問題（NP完全問題）定義：存在這樣一個NP問題， 所有的NP問題都可以約化到它。 換句話說， 只要解決了這個問題，那么所有的NP類問題都解決了。這樣的NP類問題不止一個，是一類， 這一類問題就叫做NPC問題（NP完全問題）；
2.1）NP定義： NP代表非確定型多項式時間（nondeterministic polynomimal-time）， NP類問題在難度上 遜色于不可判定問題的類；
2.2）確定型機器和非確定型機器：
- 2.2.1）確定型機器： 它在每一時刻都在執行一條指令。根據這條指令， 機器再去執行某條接下來的指令，這是唯一可以確定的；
- 2.2.2）非確定型機器：而一臺非確定型機器對其后的步驟是有選擇的。它可以自由進行它想要的任意的選擇， 如果這些后面的步驟中有一條導致問題的解，那么它將總是選擇這個正確的步驟。因此，非確定型機器具有非常好的猜測（優化）能力；
2.3）如何檢驗一個問題是否屬于 NP 的簡單方法是用 是否問題（yes/no） 的語言描述該問題？
如果我們在多項式時間內能夠證明一個問題的任意“是”的實例是正確的， 那么該問題屬于NP類問題；以哈密爾頓圈問題為荔枝， 一個“是”的實例就是圖中任意一個包含所有頂點的簡單回路， 由于給定一條路徑，驗證它是否真的是哈密爾頓是一件簡單的事情， 所以哈密爾頓圈問題是 NP類問題；
Attention）不是所有的可判定問題都屬于NP類問題。 考慮確定一個圖是否（沒有哈密爾頓圈）的問題。證明一個圖有哈密爾頓圈時相對簡單的一件事情——我們只需要展示一個即可。然后卻沒有人知道如何以多項式時間證明一個圖沒有哈密爾頓圈。似乎人們只能枚舉所有的圈并且將它們一個一個地驗證才行。因此，無哈密爾頓圈 的問題不知道屬不屬于 NP類問題；
【3】NP完全問題
3.1）NPC問題（NP完全問題）的定義：存在這樣一個NP問題， 所有的NP問題都可以規約到它。 換句話說， 只要解決了這類問題，那么所有的NP類問題都解決了。這樣的NP類問題不止一個，是一類， 這一類問題就叫做NPC問題（NP完全問題）；
3.2）如何將問題P1規約到P2：
- 3.2.1）規約描述： 設有一個映射， 使得P1 的任何實例都可以變換成P2 的一個實例。求解P2， 然后將答案映射回原始的解答。
- 3.2.2）看個荔枝： 考慮吧數以10進制輸入到一個計算器中，將這些10進制數轉化成2進制數，所有的計算都用2進制進行。然后， 再把最后答案轉變成十進制顯示。對于可多項式地歸約成P2的P1， 與變換相聯系的所有的工作必然以多項式時間完成；
3.3）NP完全問題是最難的NP問題的原因在于： 一個NP完全問題基本上可以用作NP中任何問題的子程序， 其花費只不過是多項式的開銷量；因此，如果任意NP完全問題有一個多項式時間的解， 那么NP中的每一個問題必然都有一個多項式時間的解。這使得NP完全問題是所有NP問題中最難的問題；
3.4）設我們有一個NP完全問題P1， 并設P2已知屬于NP， 證明P2也是NPC類問題。再進一步假設P1多項式地歸約成P2， 使得我們可以通過使用P2求解P1而只多損耗了 多項式時間。由于P1是NP完全問題的， NP中的每一個問題都可以多項式地歸約成P1。應用多項式的封閉性， 我們看到， NP中的每一個問題均可歸約成P2： 我們把問題歸約成P1， 然后再把P1歸約到P2， 因此P2是NP完全的；
3.5）巡回售貨員問題：
- 3.5.1）問題定義： 給定一完全圖G=（V, E）， 它的邊的值以及整數K， 是否存在一個訪問所有頂點并且 總值<= K 的簡單圈？
- 3.5.2）巡回售貨員問題的應用： 印刷電路板需要穿一些孔使得芯片、電阻器和其它的電子元件可以置入；定位所需要的時間依賴于從孔到孔間行進的距離， 定位的時間越少越好；
- 3.5.3）巡回售貨員是NPC（NP完全）問題。如何證明它是NPC問題？
為了證明它是NPC的， 我們可多項式地將哈密爾頓圈問題歸約到巡回售貨員問題。為此，可以構造一個新的圖G’， G’ 和 G 有相同的頂點。對于G’ 的每一條邊（v, w）， 如果（v, w）屬于G， 那么它就有權1， 否則權2；容易驗證， G有一個 哈密爾頓圈當且僅當G’ 有一個總權為 |V| 的巡回售貨員的巡回路線（如下圖所示）；
3.6）如何證明某個新問題是NP完全的？ 必須證明它屬于NP， 然后將一個適當的NPC問題變換到該問題；
3.7）我們不禁要問：第一個NPC問題是如何具體地被證明是NPC（NP完全）的；
3.8）引入可滿足性問題：第一個被證明是NPC問題的是 可滿足性問題， 這個可滿足性問題吧一個布爾表達式作為輸入并提問是否該表達式對式中各變量的一次賦值取值為1；
3.9）證明可滿足性問題是NPC的： 在1971年，Cook通過直接證明NP中的所有問題都可以變換成可滿足性問題而證明了可滿足性問題是 NP完全的；為此，Cook用到了對NP中每一個問題都已知的事實： NP中的每一個問題都可以用一臺非確定型計算機在多項式時間內求解；
3.10）引入圖靈機：計算機的一個形式化的模型稱作圖靈機；
Cook指出這臺機器的動作如何能夠用一個及其復雜但仍然是多項式的冗長的布爾公式來模擬。 該布爾公式為真， 當且僅當由圖靈機運行的程序對其輸入得到一個“是”的答案；
3.11）其他的NPC問題： 除開可滿足性問題外， 我們已經考察過的 哈密爾頓回路問題、巡回售貨員問題、最長路徑問題都是 NPC（NP完全）問題， 此外，還有 裝箱問題， 背包問題， 圖的著色問題以及團的問題都是著名的NPC類問題；
3.12）NPC類問題相當廣泛： including 操作系統（調度和安全）、數據庫系統、運籌學 、邏輯學特別是圖論等不同領域的問題；
總結
- 上一篇： 巴中市编号（巴中备案号）
- 下一篇： 浅谈java代理