優(yōu)化問題在磕鹽的時候經(jīng)常會遇到，其中經(jīng)常涉及到某某問題是NP的之類的論斷，因此花了一點時間整理了一下NP問題的相關知識，在研究過程中看到一篇很好的文章，因此下面的整理主要基于這篇文章《什么是P問題、NP問題和NPC問題》，有興趣的同學可以仔細閱讀原文，時間緊張的話可以直接看下面我整理的內(nèi)容。

author: @Huji

預備知識

時間復雜度

表明問題規(guī)模擴大后，程序需要的時間長度增長得有多快。程序的時間復雜度一般可以分為兩種級別：

- 多項式級的復雜度，如O(1)，O(log(n))、O（n^a）等，

- 非多項式級的，如O(a^n)、O(n!)等。后者的復雜度計算機往往不能承受。

約化(Reducibility)

簡單的說，一個問題A可以約化為問題B的含義是，可以用問題B的解法解決問題A。（個人感覺也就是說，問題A是B的一種特殊情況。）標準化的定義是，如果能找到一個變化法則，對任意一個A程序的輸入，都能按照這個法則變換成B程序的輸入，使兩程序的輸出相同，那么我們說，問題A可以約化為問題B。

例如求解一元一次方程這個問題可以約化為求解一元二次方程，即可以令對應項系數(shù)不變，二次項的系數(shù)為0，將A的問題的輸入?yún)?shù)帶入到B問題的求解程序去求解。

另外，約化還具有傳遞性，A可以化約為B，B可以約化為C，那么A也可以約化為C。

基本概念

• P Problem: 對于任意的輸入規(guī)模n，問題都可以在n的多項式時間內(nèi)得到解決；

• NP(Non-deterministic Polynomial) Problem: 可以在多項式的時間里驗證一個解的問題；

• NPC(Non-deterministic Polynomial Complete) Problem: 滿足兩個條件 (1)是一個NP問題 (2)所有的NP問題都可以約化到它

• NP-Hard Problem: 滿足NPC問題的第二條，但不一定要滿足第一條

詳解

P Problem

如果一個問題可以找到一個能在多項式的時間里解決它的算法，那么這個問題就屬于P問題，即算法的時間復雜度是多項式級的。比如n個數(shù)中間找到最大值，或者n個數(shù)排序之類的。

NP Problem

NP問題的另一個定義是可以在多項式的時間里猜到一個解的問題，例如求問圖中起點到終點是否有一條小于100個單位長度的路線，隨便選一條，如果算出來路徑小于100，那么就猜到了一個解，也就是說如果你運氣足夠好的話就可以在多項式時間內(nèi)解決這個問題。當然猜的前提是問題存在解。

再比如Hamilton問題，給定一幅圖，是否能找到一條經(jīng)過每個頂點一次且恰好一次最后又走回來的路，每條路都可以在多項式時間內(nèi)判斷這條路是否恰好經(jīng)過了每個頂點，所以也是NP問題。

很顯然，所有的P類問題都是NP問題，能在多項式時間內(nèi)解決，必然能多項式地驗證一個解。（NP是否等于P這個問題貌似還沒有定論？）

NPC Problem：

證明一個問題是NPC問題的步驟，先證明其為NP問題，再證明其中一個已知的NPC問題能夠約化到它。（由約化的傳遞性，就可以滿足定義中的第二條，第一個NPC問題是邏輯電路問題，即給定一個邏輯電路，問是否存在一種輸入使輸出為True，它顯然屬于NP問題，并且可以證明所有NP問題都可以約化到它）。

NPC問題目前沒有多項式的有效算法，只能用指數(shù)級甚至階乘級復雜度的搜索。