算法設計與分析（電子科技大學）（下）歸約與複雜度的NP問題以及近似算法

第六章 歸約與複雜度的NP問題

6.1 引入

定義：

P.Decision problems for which there is a poly-time algorithm.

NPC 如果一個問題Q，它滿足以下兩條性質：

(1). Q是NP問題

(2). 任一NP問題都可在多項式時間内歸約到問題Q

對于這一類問題，他們滿足兩個性質，一個就是在polynomial時間内可以驗證一個candidate answer是不是真正的解，另一個性質就是我們可以把任何一個NP問題在polynomial的時間内把他的input轉化，使之成為一個NP-complete問題（即規約）。NP-Complete Problem問題可以互相轉換 (在多項式時間内)，隻要其中一個問題可以在多項式時間内解決，那麼其他問題也都将可以在多項式時間内解決。

上面我們介紹了NPC問題需要滿足兩條性質，當一個問題僅滿足性質(2)，而不滿足性質(1)時，我們說該問題時NPH問題（NP-hard，NP-難問題）。

如果我們給NPC問題找到了一個多項式時間複雜度的算法，那麼也就意味着我們給所有的NP問題找到了多項式時間複雜度的算法，進而NP=P，因為P=NP，是以“P對NP問題”就可以被解決。比如背包問題是NPC問題，如果我們給背包問題找到了一個多項式時間複雜度的算法，那麼就證明了P=NP，但給NPC問題找一個多項式時間複雜度的算法太難了，是以現在人們普遍相信P≠NP。

詳細：執行個體化P NP NPC

首先對算法的設計與判别進行分類：design pattern 和 design anti-patterns

歸約

思想： 我們現在遇到了個問題，可以把它轉化到一個某個已解決的問題上，而不是一定要直接解決這個問題

概念描述： 設計一個函數f(x)，把問題A的輸入轉換成問題B的一個輸入，這樣就能用問題B的解法來求解。（輸出真或假）

A可以被歸約到B。

難點：轉換函數f(x)的設計必須要保證問題B的輸出結果和相應的問題A上的答案保持一緻。

歸約的妙用舉例：

可視化歸約

Karp 歸約、Levin 歸約、Cook 歸約這幾個概念有何聯系與差別

先考慮兩類常見的問題：搜尋型問題和判定型問題。搜尋型問題對應于一個關系R，判定型問題對應于一個集合S。

Cook歸約對這兩類問題都有效；

Karp歸約隻能應用于判定型問題，歸約的對象是集合與集合；

Levin歸約隻能應用于搜尋型問題，歸約的對象是關系與關系。事實上，Levin歸約是為了特地處理搜尋型問題，根據Karp歸約來定義的。

注：

（1）Many-one reduction是歸約的不同對象x可以映射到同一個f(x)上。 One-one reduction 是歸約不同對象x，映射到不同的f(x)上。

（2）Karp歸約與Many-one reduction 唯一的不同是它還要求函數 [公式] 是能在多項式時間内被計算出來的

Stephen Cook是NPC理論的創始者，而Richard Karp則證明了組合優化中的大多數經典問題（背包問題、覆寫問題、比對問題、分區問題、路徑問題、排程問題等）都是NPC問題。

If Cook reduction = Karp reduction then co-NP = NP.

（1）了解什麼是多項式歸約（polynomial-time reduction）

多項式時間歸約描述：在計算複雜性理論中，多項式時間歸約是指假設已有解決一個問題的子程式，利用它在多項式時間内（不考慮子程式運作所用時間）解決另一個問題的歸約方法。

多項式時間歸約：如果問題X和問題Y滿足以下兩條性質，那麼問題X可以在多項式時間歸約到問題Y。

• 問題X可以通過多項式時間的基本運算步驟轉換為問題Y；

• 問題X多項式次調用求解問題Y的算法，且問題Y可以在多項式時間内被求解。

  可以記為：X ≤p Y

  需要注意的是，問題X轉換為問題Y之後，問題Y的運作時間是建立在問題Y的輸入上。

  對于這個定義，可以簡單了解為：求解問題Y算法需要多項式時間，問題X轉換為問題Y需要多項式個基本運算加上多項式次調用求解問題Y的算法。是以總共需要的時間是：多項式 + 多項式 * 多項式。

根據以上定義，可以得到三個定理：

• 假設X ≤p Y，如果Y能夠在多項式時間内求解，那麼X也能在多項式時間内求解。
• 假設X ≤p Y，如果X不能在多項式時間内求解，那麼Y也不能在多項式時間内求解。
• 如果X ≤p Y且Y ≤p X，那麼X和Y是等價的。

（2）知道怎樣從一個問題多項式歸約到另一個問題，需要熟悉的歸約包括：從點覆寫問題到獨立集問題，從3-SAT問題到獨立集問題等基本歸約。

多項式時間歸約的一般方法：

1. 簡單的恒等歸約：比如最大獨立集和最小點覆寫。

顯然{2, 3, 7}恰好跟最大獨立集 {1, 4, 5, 6}互補。這是因為在independent set中，任意2個結點<u,v>都不會有一條邊相連，是以與u,v相連的結點一定在集合外面，是以independent set的補集一定是vertex cover的。

1. 從特殊情況到一般情況：比如點覆寫 ≤p 集合覆寫。

集合覆寫問題：

問題定義：

執行個體：現在有一個集合A，其中包含了m個元素（注意，集合是無序的，并且包含的元素也是不相同的），現在n個集合，分别為B1、B2、…、Bn。并且這n個集合的并集恰好等于A集合，即：B1UB2UB3U…UBn=A。

問題：是否存在B集合的最小子集，且他們的并集也等于A集合？

例子：集合A={1,2,3,4,5}，集合B={{1,2,3},{2,4},{3,4},{4,5}}。可以看出，B集合的并集恰好等于A集合，那麼問題的解是：SETCOVER={{1,2,3},{4,5}}。

頂點覆寫問題：是否存在V的子集V’，使得|V’|<=|V|，并且G中的每條邊e，至少有一個頂點在V’中？

1. 利用零件編碼gadgets：比如3-SAT ≤p 獨立集。（問題（5））

（3）要求掌握同一個問題的最優問題如何多項式時間歸約到該問題的判斷問題（自身歸約）；

自歸約：将求解問題歸約成判斷問題，如果判斷問題能夠解決，那麼就可以利用判斷問題來解決求解問題。

比如最小點覆寫問題，假如我們能判斷一個圖中是否存在點數為k的最小點覆寫。于是可以周遊圖中的每個頂點，如果删去這個頂點以及和這個頂點相連接配接的邊，圖中隻存在點數為k-1的點覆寫，那麼就可以判定該頂點是最小點覆寫中的頂點，不斷重複這個操作，就可以找到最小點覆寫。

（4）熟悉NP和NPC的概念

以目前的技術是很難給出有效的多項式解法，這些問題就是NP完全問題，比如0-1背包問題。

常見求解NPC問題的思路：設計啟發式的算法、近似解、使用指數級複雜度算法。

證明NP問題。這個容易，即給你一個結果，你能在polynomial的時間内驗證該結果的正确性。

證明NP-hard問題。我們要證明一個問題是NP-hard的時候，我們通常要做的是找到一個已被證明了的NPC問題，并把這個NPC問題歸約到該問題上去（即NPC<=NP-hard）。

證明NP-Complete問題。分以下兩步：

第一步，證明這個問題屬于NP；

第二步，證明這個問題是NP-hard的。

所有的NP問題都可以規約到SAT(即NP<=SAT)，也就是說SAT至少與NP問題一樣難，或者如果解決了3SAT問題，所有的NP問題就解決了。

（5）記住證明一個問題屬于NPC的基本步驟

證明NP-Complete問題。分以下兩步：

第一步，證明這個問題Y屬于NP；

第二步，選擇一個問題NP-C，X問題

第三步，證明X問題可以多項式歸約到Y。

（另：step2改為，直接證Y問題是NP-H，也是可以，但是要困難點）

規約關系具有傳遞性，是以有3SAT<=Vertex Cover，NP<=NP-Complete。 事實上，由于NP-Complete⊂ NP 且 NP<=NP-Complete，可以推導出 所有的NP-Complete 可以互相規約，也就是所有的NP-Complete都是等價的。

關于SAT

Reducing SAT to Shortest Clique Problem

Reducing SAT to Shortest Tour Problem

NP-Complete間的規約例子

1. 3SAT<=Independent Set

簡單的說，構造好這樣的圖後，我們想要給每個三角形指派， 每條邊是 沖突的，例如我們選擇第一個三角形的y為真值後，與y相連的各個頂點将不能被選擇。

加入了3m個點，3m+k條邊是以是多項式的時間内完成的規約。

8. Vertex Cover <=Independent Set

9. Independent Set <= Clique problem

2. 3SAT <= Vertex Cover

3. 3SAT <= ILP

4. 3SAT <= Hamiltonian cycle problem

11. Subset sum problem <= Partition problem

12. Clique problem<=Subgraph isomorphism problem

13. Partition problem <= Knapsack problem

14. Hamiltonian cycle problem <= Hamiltonian path problem

15. Hamiltonian cycle problem <= Traveling salesman problem

（6）能證明一個問題是NP-hard

證明NP-hard問題。我們要證明一個問題是NP-hard的時候，我們通常要做的是找到一個已被證明了的NPC問題，并把這個NPC問題歸約到該問題上去（即NPC<=NP-hard）。

簡單說就是：

1）對問題A給定限制條件得到一個特例B問題

2）證明問題B是NPC問題。

第七章 近似算法

（1）了解什麼是近似算法；

意義：所有已知的解決baiNP-難問題算法都有指數型運作時du間。但zhi是，如果我們要找一個“好”解dao而非最優解，有時候多項式算法是存在的。

迄今為止，所有的NP完全問題都還沒有多項式時間算法。

對于這類問題，通常可采取以下幾種解題政策。

(1)隻對問題的特殊執行個體求解

(2)用動态規劃法或分支限界法求解

(3)用機率算法求解

(4)隻求近似解

(5)用啟發式方法求解

近似算法關注的三個方面：

（1）解的優越性，即是否能達到最優解

（2）算法的效率，即複雜度（能否在多項式時間内完成）

（3）算法适用的範圍，即是否适用于所有情況，還是隻适合特殊情形

一般的算法在這三個方面往往不能同時表現得很好，但是我們可以退而求其次，選擇其中得兩個方面去盡可能地滿足，當我們選擇滿足後兩者，即對解的優越性放寬要求時，設計出的算法被稱為近似算法。

（2）熟悉load balancing 問題的近似算法；

（3）了解點覆寫問題的定價算法（Pricing method），證明該方法能得到一個2倍近似解；

（4）了解點覆寫問題的整數規劃模型如何建立，了解松弛求解方法；

（5）要求會對一個圖問題建立整數規劃模型（以點覆寫問題為例）

算法設計與分析（電子科技大學）（上）算法基礎和貪心算法

算法設計與分析（電子科技大學）（中）分治算法、動态規劃以及最大流問題和最小分割問題