NP問題及其相關内容介紹

NP問題及其相關介紹

• NP問題及其相關介紹
  • 分類
  • 概念
    • P問題
    • NP問題
    • 約化
    • NP完全問題
    • NP難問題
  • 結論

分類

• P問題
• NP問題
• NP完全問題
• NP難問題

概念

P問題

NP問題

約化

約化（Reducibility，有的資料上叫“歸約”）。簡單地說，一個問題A可以約化為問題B的含義即是，可以用問題B的解法解決問題A，或者說，問題A可以“變成”問題B。《算法導論》上舉了這麼一個例子。比如說，現在有兩個問題：求解一個一進制一次方程和求解一個一進制二次方程。那麼我們說，前者可以約化為後者，意即知道如何解一個一進制二次方程那麼一定能解出一進制一次方程。我們可以寫出兩個程式分别對應兩個問題，那麼我們能找到一個“規則”，按照這個規則把解一進制一次方程程式的輸入資料變一下，用在解一進制二次方程的程式上，兩個程式總能得到一樣的結果。這個規則即是：兩個方程的對應項系數不變，一進制二次方程的二次項系數為0。按照這個規則把前一個問題轉換成後一個問題，兩個問題就等價了。

很顯然，約化具有一項重要的性質：約化具有傳遞性。如果問題A可約化為問題B，問題B可約化為問題C，則問題A一定可約化為問題C。 當然，我們所說的“可約化”是指的可“多項式地”約化(Polynomial-time Reducible)，即變換輸入的方法是能在多項式的時間裡完成的。約化的過程隻有用多項式的時間完成才有意義。

NP完全問題

從約化的定義中我們看到，一個問題約化為另一個問題，時間複雜度增加了，問題的應用範圍也增大了。通過對某些問題的不斷約化，我們能夠不斷尋找複雜度更高，但應用範圍更廣的算法來代替複雜度雖然低，但隻能用于很小的一類問題的算法。再回想前面講的P和NP問題，聯想起約化的傳遞性，自然地，我們會想問，如果不斷地約化上去，不斷找到能“通吃”若幹小NP問題的一個稍複雜的大NP問題，那麼最後是否有可能找到一個時間複雜度最高，并且能“通吃”所有的 NP問題的這樣一個超級NP問題？答案居然是肯定的。也就是說，存在這樣一個NP問題，所有的NP問題都可以約化成它。換句話說，隻要解決了這個問題，那麼所有的NP問題都解決了。這種問題的存在難以置信，并且更加不可思議的是，這種問題不隻一個，它有很多個，它是一類問題。這一類問題就是傳說中的NPC 問題，也就是NP-完全問題。NPC問題的出現使整個NP問題的研究得到了飛躍式的發展。

NPC問題的定義非常簡單。同時滿足下面兩個條件的問題就是NPC問題。首先，它得是一個NP問題；然後，所有的NP問題都可以約化到它。

NP難問題

順便講一下NP-Hard問題。NP-Hard問題是這樣一種問題，它滿足NPC問題定義的第二條但不一定要滿足第一條（就是說，NP-Hard問題要比 NPC問題的範圍廣）

結論

• 所有的P類問題都是NP問題
• 雖無法證明NP=P，但人們普遍相信NP不等于P，因為有NP完全問題的存在