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

author: @Huji

預(yù)備知識(shí)

時(shí)間復(fù)雜度

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

- 多項(xiàng)式級(jí)的復(fù)雜度，如O(1)，O(log(n))、O（n^a）等，

- 非多項(xiàng)式級(jí)的，如O(a^n)、O(n!)等。后者的復(fù)雜度計(jì)算機(jī)往往不能承受。

約化(Reducibility)

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

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

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

基本概念

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

• NP(Non-deterministic Polynomial) Problem: 可以在多項(xiàng)式的時(shí)間里驗(yàn)證一個(gè)解的問題；

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

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

詳解

P Problem

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

NP Problem

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

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

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

NPC Problem：

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

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