藍色情懷

論P,NP,NP-hard,NP-complete問題

定義:

        基本上這世界上的問題可以分類成為
        1) Unsolvable Problem
        2) Intractable Problem
        3) NP-Problem
        4) P-Problem

        第一種是無解之問題
        第二種是需要 exponential time (即是 O(2^n) 以上等級) 才可以解決的問題
        第三種是 所謂的 NP (後論)
        第四種是 easy problem

P: 指的是有 Polynomial Time 的解的問題。
NP:　指的是還沒有找到 Polynomial Time 的解，也不確定有沒有 Polynomial Time 的解，但是你一旦提供一個解，這個解可以在 Polynomial Time 被驗證的問題。
NP Complete: 指的也是還沒有找到 Polynomial Time 的解，但是可以在 Polynomial Time 被驗證的問題。但是NPC的問題是NP裡面比較難的問題，所以如果能夠證明NPC的問題有P的解，那NP的問題就都可以找到P的解。
NP Hard:　指的也是還沒有找到 Polynomial Time 的解，但是不確定是不是能在 Polynomial Time 被驗證的問題。NP Hard的問題又比NPC難。

一般來說 P 的問題算是比較簡單，NP Complete 跟 NP Hard 算是很難的問題。而 NP 的問題還是有可能找到快速算法。

假設P ≠ NP的複雜度類的圖解。如P =NP則三個類相同。

        P : a problem can solved in Polynomially time
            因此 P 是指 Polynomially time 的 P (多項式時間 即 O(n^k),k為一常數)

        NP-Problem:
           existed Non-deterministic algorithm can solved this problem
           in Polynomially time
           (有一非確定演算法可以解此問題,但是在多項式時間內解之)

        要談 NP-hard 與 NP-complete 前先要談談 reducible
        不然很難定義

        reducible:
        存在有兩問題 p1,p2
        若p1可以在 polynomially time reduce 成為p2
        則稱p1,p2是poylnomially reducible

        再來定義

        NP-hard:
        若 All NP problem can polynomially reduce 成為 Q
        則 我們稱 Q 這個問題 有 NP 這麼難 ,即為NP-hard

        NP-complete:
        同時是 NP,同時是 NP-hard 稱之..

  ^NP,NP-hard 之交集為NP-complete，P 在 NP 裡

        舉例:
        P : sorting
        NP : Hamitonian path
        NP-hard : Halting Problem
                  (有的書認為halting是無解問題,我問過別的老師,他認為是NP-hard)
        NP-complete : SAT

對NP -Hard問題和NP-Complete問題的一個直觀的理解就是指那些很難（很可能是不可能）找到多項式時間算法的問題。

因此一般初學算法的人都會問這樣一個問題：NP-Hard和NP-Complete有什麼不同？根據定義，如果所有NP問題都可以多項式歸約到問題A，那麼問題A就是NP -Hard；如果問題A既是NP-Hard又是NP，那麼它就是NP-Complete。NP-Hard問題類包含了NP- Complete。
 

NP-Complete is a subset of NP-Complete. 

Halting problem 是NP-Hard而不是NP-Complete。

P問題：可以用polynomial演算法解決的問題，亦即解決時間為polynomial時間。
NP問題：可以用non-deterministic polynomial演算法解決的問題。請注意，P問題既然可以用polynomial演算法解決，當然也可以用non-deterministic polynomial演算法解決 ,因此所有的P問題都是NP問題。

NP-HARD：一個NP問題經由polynomial演算法轉化之後所成的問題。此處的轉化，一般稱為reduce。NP-COMPLETE：一個NP問題經由polynomial演算法轉化之後，仍為NP問題。換句話說，所謂的NP-COMPLETE問題，就是既為NP-HARD，亦為NP。也就是說，若只經由polynomial演算法來reduce，不論如何都在NP的範圍內。

NP-HARD與NP-COMPLETE的不同，在於NP-HARD不一定屬於NP問題。 NP-HARD可以是NP問題，也可以是一個超越NP難度的問題.... 但若是NP-HARD的難度仍然是NP，則這個NP-HARD就是一個NP-COMPLETE。

先稍微說明一下 polynomial time reduction 的概念好了,假設有 A,B 兩個問題, 如果我們有一個演算法可以解決 B 問題,那麼我們可以利用此演算法在 polynomial time 內也解決 A 問題,則我們就說 A 可以 reduce 到 B,也就是說假如 B 解決了, A 也可以很容易的解決..(可以想成是 B 比 A 難) 但正確的說是：A reduce to B 應該是說我們可以設計一個Poly-time 的 Algorithm將A的問題轉成B問題的型式,

For example, 所有satisfiability problem都可以reduce到3-SAT problem.如: (x1 V x2) => (x1 V x2 V y1), (x1 V x2 V -y1) -x3 => (-x3 V y1 V y3), (-x3 V -y1 V y3), (-x3 V y1 V -y3), (-x3 -y1 V -y3) (x1 V -X2 V X3 V x4) => (x1 V -x2 V y1), (x3 V x4 V -y1) 故, 如果我們可以在P time裡解3-SAT則也可以用此方法解satisfiability problem. 也就是說如果我們不可以在P-time裡解SAT problem則也無法在p-time解3-SAT problem 如果一個問題屬於 NP-hard, 那麼所有屬於 NP 的問題都要能reduce 到這個問題上面, 也就是說這個問題比所有 NP 的問題都要更難. 如果一個問題是 NP-complete, 兩個條件:(1) 此問題屬於 NP (2) 此問題為 NP-hard 也就是說, NP 的問題裡面, 有一部份是最難的,所有其他的 NP 問題都能 reduce 到這些問題上面這一群問題就稱為 NP-complete 的問題! 所以 NP-hard 和 NP-complete 都是比所有 NP 問題都還要難的問題,差別在於 NP-complete 還是在 NP 之內, 是 NP-hard 裡面屬於 NP 的問題!

面對一個問題，不管是什麼問題，我們都會想個方法來去解決它。有些問題有解，有些問題無解，有些很好解，有些卻很難解。今天要介紹的主題，是要對世界上所有的問題來做一個分類，什麼叫難的問題，什麼叫簡單的問題。

唸計算機科學的都會碰到這個令人頭痛的章節...雖然很心不甘情不願的去搞懂這東西，但如果有了這個知識是可以讓我們在面對一個未知的問題時，能夠從容且理性地來進行分析解題。

關於NP-Complete的解釋，演算法的聖經本 -- Cormen等人所著作的"Introduction to Algorithms"在第34章有說明，但那只是大略性的說明，第一次接觸NP問題的人大多會看不懂在寫什麼。其實應該要去看計算理論相關的書才能清楚的瞭解NP-Complete的問題，如Sipser的 " Introduction to the Theory Of Computation"第7章，以及Papadimitriou 的 "Computational Complexity"第九章。

為了描述一個問題，我們一定可以用各種有限的符號、文字來描述，所以一個問題可以變成一串文字，也就是字串(String)。現在我們想要對問題進行處理，我們會先把問題各別以字串來描述，又為了判斷這些字串(問題)是否符合某種條件並進行適當的運算，於是我們會設計一台機器(machine)，這裡所謂的機器泛指一種處理程序，並不一定是冷冰冰的實體機械。若符合條件的字串，可以被這台機器所接受(accept)，那麼我們就稱這台機器能認識(recognize)這字串， 能被這台機器所認識的字串集合就稱為這台機器的語言(Language)。所謂接受(accept)就是屬於這機器的語言之字串，機器可以判讀並回傳結果。反之，不屬於這機器的語言之字串，機器可以判讀並回傳結果，我們稱這字串被機器所拒絕(reject)。注意語言只要符合"認識"的條件即可，所謂"認識"就是這語言可被機器接受，也就是問題若有符合條件的解答，此機器可以找得到。但若此語言不被接受，也就是問題的解答若是不符條件，機器可能找不出來，永遠得不到機器回傳的結果，就像當機一樣。如果機器能接受亦能拒絕任一輸入字串，我們稱這機器可決定(decide)一語言，此語言可被機器決定(decidable)。

這台機器的運作過程會有許多狀態，也就是許多步驟、流程。如果這台機器的步驟及接受的字元種類是有限的，也就是數量是可數的，並面對所有字元都能對應一種狀態，而且具有起始及結束的狀態，那麼我們稱這台機器叫”有限狀態機”(Finite Automaton)。能夠被有限狀態機認識的語言，我們稱這語言叫正規語言(Regular Language)。機器在處理各種輸入從開始到結束，會有一連串的狀態組合，若這些狀態是一個接著一個，不會有一個狀態後面是接兩個狀態以上，我們稱這機器為"決定性機器" (deterministic machine) ，反之，若有一個狀態後面是接兩個狀態以上之情形，我們稱這機器為"非決定性機器" (nondeterministic machine) 。我們可以想像成決定性機器如同只含有一顆CPU的電腦，非決定性機器就是含有好幾顆CPU可做平行處理的電腦。所以，哪種機器能力比較強大？當然是非決定性機器了，你可以把它想像成是具有無限多顆CPU的電腦，只是，這種電腦並不存在世界上。

接下來要評估機器的執行時間，我們可以用一函數 f(n) 來描述這機器的最大執行時間，其中 n 為輸入字串的字元數，f(n)稱為此機器的時間複雜度 (time complexity)。然而 f(n) 可能是一個很複雜的函數，我們有時在分析上並不需要看到太多的細節，於是我們用以下三種漸近記號(asymptotic notation)來對時間複雜度進行分類：

    O(g(n)) = {f(n)| 存在兩個正常數 c 及 n0 使得當所有 n ≧ n0 時，0 ≦ f(n) ≦ cg(n) } 
    Ω(g(n)) = {f(n)| 存在兩個正常數 c 及 n0 使得當所有 n ≧ n0 時，0 ≦ cg(n) ≦ f(n) } 
    θ(g(n)) = {f(n)| 存在三個正常數 c1, c2 及 n0 使得當所有 n ≧ n0 時，0 ≦ c1g(n) ≦ f(n) ≦c2g(n)}

例如：5n³ + 2n² + 22n + 6 = O( n³ )，當 n ≧ 10, c = 6 時

如果時間複雜度為一多項式，也就是 O( n^k )，k 為一常數，則稱為多項式時間複雜度。

機器除了可以解決問題，也可以轉換問題。若兩個不相干的問題A及B，可以透過一種機器來轉換，使得解A問題可透過解B問題的機器來求解，我們稱這樣的轉換行為叫簡化 ( reduction )，記為：

    A £_m B

若是這部簡化的機器具有多項式時間複雜度，那這樣的簡化稱為可多項式時間簡化 (polynomial time reduction)，記為：

    A £_p B

以上介紹了許多在解決問題的行為中會遇到的一些現象，接下來回到對問題分類的主題。

有一種問題，我們可以設計出一種具有多項式時間複雜度的決定性機器來解決，這種問題就稱為 P 問題，P是 Polynomial time 的意思。另外有一種問題，我們不知道能否設計出一種具有多項式時間複雜度的決定性機器來解決，但我們確定可以設計出具有多項式時間複雜度的非決定性機器來解決，且可以設計出具有多項式時間複雜度的決定性機器來驗證任意一個答案是否為此問題的解答，也就是我們可以亂猜一個答案，然後能在多項式時間內驗證是否為正確解答。這樣的問題我們稱為 NP 問題，NP是 Nondeterministic Polynomial time 的意思。

那麼 P 跟 NP 之間有什麼關係，從上面的敘述可知，P一定是屬於 NP的一種。但是，NP 是屬於 P的一種嗎？如果是，那麼就會 P = NP。這個問題是世界八大難題之一，目前已有兩題被解開，一是普安卡雷猜想 (The Poincare Conjecture) ，另一是費瑪最後定理 (Fermat's Last Theorem)，至於P ?= NP這問題則是尚未有人解開。

還有一種問題，我們除了不知道該怎麼設計出多項式時間複雜度的決定性機器，而且也不知道該怎麼設計出多項式時間複雜度的決定性機器來驗證任意答案，很明顯地，這種問題一定不屬於 NP 問題。但是我們卻發現，所有的NP問題都可以在多項式時間簡化成這種問題，這種問題就叫 NP-Hard 。為什麼叫 hard，因為它們連驗證答案都是不容易的。

最後一種問題，它們跟NP-Hard很像，也是所有的NP問題都可以在多項式時間簡化成這種問題。不同的是，我們可在多項式時間內驗證答案，也就是這種問題是屬於 NP。那麼我們稱這種問題叫 NP-Complete。它們是整個NP問題最具代表性的，所有NP問題都能簡化成它們，若是我們可以對NP-Complete的其中一個問題找到一個多項式時間的演算法，那麼 NP就會等於 P了，只是目前還沒有人找到而已。

我們要判斷一個問題 A 是否屬於NP-Complete，難道要將所有的NP問題一個個簡化過來嗎？其實不用，假若我們已知有一個問題 B 為NP-Complete，我們只要能將 B 多項式時間內簡化成 A ，那麼A就是屬於NP-Complete了。萬流歸宗，總會有一個問題是所有NP-Complete的簡化始祖。第一個被發現的NP-Complete問題是SAT問題，這是 cook 在1971年提出，SAT問題就是對一個布林代數式去找出各變數的值使得結果會是 true。證明SAT問題是NP-Complete並不太容易，請參考Sipser的 " Introduction to the Theory Of Computation, 2ed"第7章。我們只要知道SAT是NP-Complete就好，然後用它來證明其它的NP-Complete問題。

3SAT問題：
若一布林代數式可以這樣表式：(x₁ v x₂ v x₃ ) ^ (x₄ v !x₅ v x₆) ^ ... ^ (x₂ v !x₄ v x₆)，其中 v是or運算，^是and運算。這種布林代數式叫 3-CNF (3- conjunctive normal form)，也就是從有限的變數集合中，將各變數以三個為一組or在一起，然後以and將各組變數連接在一起。如何從3-CNF找出各變數的值，使得3-CNF會等於true，這問題是一種NP-Complete問題，證明如下，請注意證明的步驟：

(1)先證明3SAT為NP問題。由於變數的個數是有限的，對任一組n個變數的值，我們只要代入3-CNF式，就知道是否為true， 頂多為O(n)的時間，因此 3-SAT 為NP問題

(2) 證明 SAT £_p 3SAT。要先這樣想，假設我們已設計出3SAT的演算法，我們只要將給SAT問題的輸入以多項式時間轉成3SAT問題的輸入格式，那麼3SAT可以找出一解即代表是SAT的解。
考慮一組or的運算之變數個數則有以下這些情形：

1 個變數的 or
(x) = (x v x v x)
2 個變數的 or
(x₁ v x₂) = (x₁ v x₂ v x₁)  
大於3個變數的 or
(x₁ v x₂ v ... v x_n ) = (x₁ v x₂ v y₁ ) ^ (!y₁ v x₃ v y₂ ) ^ (!y₂ v x₄ v y₃ ) ^ ... ^ (!y_n-3 v x_n-1 v x_n )
,其中 y_i 為新增的變數。

如此完成簡化，且這樣的簡化過程皆在O(n)時間內完成。

根據(1), (2) 3SAT為NP-Complete

以上為對NP-Complete做一個簡單的介紹，如想知道更多細節的內容可以參考這三本書：

[1] C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.

[2] M. Sipser. Introduction to the Theory of Computation, 2ed. Thomson, 2005.

[3] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 2ed, The MIT Press, 2001.