? ? 我們在閱讀paper時，經(jīng)常會看到NP-hard，NP-complete等問題。我也是慢慢學習發(fā)現(xiàn)到這些問題的趣味，下面我們一起來探討一下P，NP，NP-hard，NP-complete這些問題吧！在正式進入之前，先簡單列出一波常見的概念。

1.時間復雜度

? ? 在遇到算法問題時，就不可避免的需要討論算法的時間復雜度。算法的時間復雜度可以用來度量算法的運行時間。算法的時間復雜度反映了程序執(zhí)行時間隨輸入規(guī)模增長而增長的量級，在很大程度上能很好反映出算法的優(yōu)劣程度。說白了，時間復雜度也就可以表示為對于高速處理數(shù)據(jù)的計算機來說，處理某一個特定數(shù)據(jù)的效率不能衡量一個程序的好壞，而應該看當這個數(shù)據(jù)的規(guī)模變大到數(shù)百（或萬）倍后，程序運行時間是否還是一樣，或者也跟著慢了數(shù)百（或萬）倍。

? ? 每個問題有自己的規(guī)模，假設n為問題的規(guī)模，當n不斷變化時，時間頻度T(n)也會不斷變化。一般情況下，算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，用T(n)表示，若有某個輔助函數(shù)f(n),使得當n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=Ｏ(f(n)),稱Ｏ(f(n))?為算法的漸進時間復雜度，簡稱時間復雜度。

? ? 通常復雜度被分為兩種級別，一種是多項式級復雜度（形如O(1)，O(log(n))，O(n^a)），另一種是非多項式級復雜度（形如O(a^n)，O(n!)）。一般來說我們選擇的算法通常都需要是多項式級的復雜度，非多項式級的復雜度需要的時間太多，往往會超時，除非是數(shù)據(jù)規(guī)模非常小。

2.什么是P問題、NP問題？

? ? 首先，簡單直觀的說什么是P問題？如果一個問題可以找到一個能在多項式的時間里解決它的算法，那么這個問題就屬于P問題。P問題也叫做多項式問題。

? ?NP問題是指可以在多項式的時間里驗證一個解的問題。注意NP問題不是非P問題！有一個著名的NP問題：旅行家推銷問題(TSP)。簡述如下：

? ?即有一個推銷員，要到n個城市推銷商品，他要找出一個包含所有n個城市的環(huán)路，這個環(huán)路路徑小于a。我們知道這個問題如果單純的用枚舉法來列舉的話會有種，這已經(jīng)不是多項式時間的算法了。那怎么辦呢？我們可以用猜的，假設人品爆炸猜幾次就猜中了一條小于長度a的路徑，TSP問題解決了。但是實際上，我們不可能每次都猜的準，或許我們猜幾次能猜出來，或許我們把所有路徑都猜一遍也猜不出來？所以我們說，這是一個NP類問題。也就是，我們能在多項式的時間內(nèi)驗證并得出問題的正確解，可是我們卻不知道該問題是否存在一個多項式時間的算法，每次都能解決它(注意，這里是不知道，不是不存在！)。

? 那么由此可以引出一個疑問至今的問題：NP問題=？P問題（NP類問題是否等于P類問題？）。也就是說是否我們能在多項式時間內(nèi)得到的解能夠用計算機上的多項式算法解決呢？那么這樣的話，所有問題都能用計算機上的算法解決咯?在講清這個問題前，我們需要了解規(guī)約（或約化）的概念。

3.什么是規(guī)約（或約化）？

? ? 科學家在解決上述問題時，首先引入約化的概念。一個問題A可以約化為問題B的含義即是，可以用問題B的解法解決問題A，或者說，問題A可以“變成”問題B。也就是說B的解法能同時解決問題A和問題B，問題A可以約化為問題B。這個示例說明什么呢？A的時間復雜度是≥B的時間復雜度。這樣的話，相當于我們用問題B簡化了問題A。

? ?除了約化的概念反應的物理意義外，約化還有一個重要的性質(zhì)：傳遞性！如果A問題可以約化為B，B問題可以約化為C問題，那么可以得出結論，A問題一定可以約化為問題C。但是注意，約化的過程只能在多項式的時間內(nèi)完成才有意義，如果不是“多項式”約化，而是非多項式的約化，這個約化過程就完全沒有意義。所以要注意約化的范圍！

? ?參考前面時間復雜度的概念，我們也可以直接觀察到，約化所帶來的時間復雜度的增加，能處理的范圍也變大。所以我們可以通過對某些問題的不斷約化，通過增加算法的時間復雜度，增大適用范圍，來取代一些適用范圍小，沒有什么實際適用績效的算法。

4.什么是NPC問題、NP-hard問題？

? ?在了解了約化的概念后，一個很不可思議的概念出現(xiàn)了，那就是NPC問題。到底什么是NPC問題呢？我們有NP問題，那么我們? 能不能通過一步步約化NP問題，讓它變成一個能解決掉所有NP問題的“主”NP問題呢？答案是：這個“主”NP問題是存在的。這個“主”NP問題=NPC問題（NP-Complete問題），注意NPC問題指的是一大類的問題，而不是一個問題！

? ? 前面已經(jīng)講了NP問題滿足的兩點條件，這里NPC問題滿足的條件是：（1）該問題必須是一個NP問題；（2）所有的NP問題都可以約化到該問題。

? ??那么事實上，我們對于問題的解決方法已經(jīng)大致明了，NPC問題是由所有的NP問題約化得到的，那么我們只要找到NPC的一個“解”（也就是一個多項式算法），那么所有的NP問題就能解決！這個時候P=NP，但正是因為給NPC找一個多項式算法太難太難（這里是指想要一個時間復雜度為多項式級的算法是很難很難的），所以人們相信P≠NP。

? ?那什么是NP-hard問題呢？NP-hard問題滿足NPC問題定義的第二條但不一定要滿足第一條，即NP-hard問題可以通過所有的NP問題都可以約化，但它不一定是NP問題（就是說，NP-Hard問題要比 NPC問題的范圍廣）。

?

總結

以上是生活随笔為你收集整理的到底什么是P问题，NP问题，NPC问题，NP-hard问题？什么是规约（或约化）？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。