??????學算法學到這章，真是神仙打架。上網學習各位前輩的文章，看的我也是眼花繚亂。終于看到一篇易于理解的（網址附于文末），看過之后寫寫自己的理解。如有錯誤，請各位前輩指正！

??????P問題，在這里不說全稱了，感覺說了也沒用。P問題就是指能在多項式時間求解出的問題。舉個例子：排序問題，二分查找問題的時間復雜度分別是O（nlogn）,O(logn)。

??????說到時間復雜度，這篇文章對此也做了詳細的解釋，成功刷新了我對于時間復雜度的理解，原文如下，再次引用：

??????“時間復雜度并不是表示一個程序解決問題需要花多少時間，而是當問題規模擴大后，程序需要的時間長度增長得有多快。也就是說，對于高速處理數據的計算機來說，處理某一個特定數據的效率不能衡量一個程序的好壞，而應該看當這個數據的規模變大到數百倍后，程序運行時間是否還是一樣，或者也跟著慢了數百倍，或者變慢了數萬倍。不管數據有多大，程序處理花的時間始終是那么多的，我們就說這個程序很好，具有O(1)的時間復雜度，也稱常數級復雜度；數據規模變得有多大，花的時間也跟著變得有多長，這個程序的時間復雜度就是O(n)，比如找n個數中的最大值；而像冒泡排序、插入排序等，數據擴大2倍，時間變慢4倍的，屬于O(n^2)的復雜度。”

??????NP問題就是不能確定是否能夠在多項式時間內找到一個解。但若給出一個解，能在多項式時間內證明這個解是否正確（學名叫判定性問題）。定義的前半句有兩層含義：可能找得到解，也可能找不到解。找得到解問題就變成了P問題。所以P問題屬于NP問題(P問題是NP問題的真子集)

??????NPC問題，說到NPC問題，就要提到一個操作叫“規約”。這里有一個易受誤導的地方，規約不是越化越簡單，反而是越化越難。舉個例子：A是求解一元一次函數，B是求解一元二次函數。可以說A可規約至B，因為會解B，一定會解A。可把A看作是二次項系數為0的B。所以，每規約一步，問題就變得越復雜。規約具有傳遞性：A規約至B，B規約至C，那么A規約至C。問題來了，那么一直規約下去會得到什么呢？這就是NPC問題！

??????NPC問題上文有所介紹，它是由NP問題不斷規約得來。首先NPC本身是一個NP問題，這是證明一個問題是NPC問題的首要條件。有NPC和NP問題之間的關系，可以看出：如果一個NPC問題得到了證明，那么所有可以規約至該NPC的NP問題都得到了證明。到目前為止，部分NPC問題得到了證明，但還有很多未證明。也有人把這些問題稱之為信息學的“巔峰”。（一猜也知道是很難的！）下面介紹一下證明一個問題是NPC問題的方法：

第一步：證明這個問題是一個NP問題

第二步：證明一個已知的NP問題能夠規約到該問題。

??????NP-Hard問題，就是滿足NPC問題的第二個條件，但是卻不一定滿足第一個條件的問題。任意NP問題都可以在多項式的時間內規約至NP-Hard問題。但像上文說的，NP-Hard問題不一定是NP問題。通俗點說，NP-Hard問題就是至少和NPC問題一樣難。可能是NPC也可能不是NPC（這取決于NP-Hard問題是否為NP問題）。

??????Co-NP問題是由補問題屬于NP問題的問題組成。對于co-NP問題上網差了一些資料。主要的研究方向好像是co-NP問題和NP問題的關系。鑒于水平有限，實在是看不懂，就此作罷！還望高手指點。

??????最后貼一張書上的圖，說明各類問題之間的關系：

參考網址：blog.sina.com.cn/s/blog_53bbb4b90101ckkq.htmllink
（該網址的主人也是轉載的，原主人的網址有權限。無法訪問，請原主人諒解）

總結

以上是生活随笔為你收集整理的P,NP,NPC,NP-Hard,co-NP问题辨析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。