P、NP、NPC（NP完全問題）、NP-hard問題概述

• • 一、概念總結(jié)
    
    
  • • • • 1.P問題: 能在多項式時間內(nèi)解決的問題
          
        • 2.NP問題: 不能在多項式時間內(nèi)解決或不確定能不能在多項式時間內(nèi)解決，但能在多項式時間驗證的問題
          
          
        • 3.NPC: NP完全問題，所有NP問題在多項式時間內(nèi)都能約化(Reducibility)到它的NP問題，即解決了此NPC問題，所有NP問題也都得到解決。
          
        • 4.NP hard:NP難問題，所有NP問題在多項式時間內(nèi)都能約化(Reducibility)到它的問題(不一定是NP問題)。
          
          
  • 二、四者聯(lián)系的圖形表示
    
    
    

最近在做壓縮感知的相關(guān)研究，一直對P、NP等問題一知半解，知道看到了這幾篇博文才算真正了解了這幾大問題的差異。
博文地址如下：

第一篇詳細做了這些問題的總結(jié)與講解，第二篇是一個簡短的概述。
https://blog.csdn.net/jbb0523/article/details/40710449
http://www.cnblogs.com/jpcflyer/archive/2012/04/15/2450622.html）

本篇博文主要為了自己在想到時再回顧這些概念做了個梳理總結(jié)

一、概念總結(jié)

1.P問題: 能在多項式時間內(nèi)解決的問題

一般而言，多項式時間可解意味著時間復雜度為O(1)、O(n)、O(logn)

時間復雜度并不是表示一個程序解決問題需要花多少時間，而是當問題規(guī)模擴大后，程序需要的時間長度增長得有多快。

2.NP問題: 不能在多項式時間內(nèi)解決或不確定能不能在多項式時間內(nèi)解決，但能在多項式時間驗證的問題

3.NPC: NP完全問題，所有NP問題在多項式時間內(nèi)都能約化(Reducibility)到它的NP問題，即解決了此NPC問題，所有NP問題也都得到解決。

NPC問題包含2部分：1.它是個NP問題、2.所有的問題都可以約化到它

補充：約化的概念
一個問題A可以約化為問題B的含義即是，可以用問題B的解法解決問題A
從時間復雜度來講，就是B問題的時間復雜度大于或等于A問題的時間復雜度，可以用求解B問題的算法來求解A問題。

4.NP hard:NP難問題，所有NP問題在多項式時間內(nèi)都能約化(Reducibility)到它的問題(不一定是NP問題)。

NP-hard問題滿足NPC問題的第二個條件但不滿足第一個條件。

二、四者聯(lián)系的圖形表示

P問題屬于NP問題，NPC問題屬于NP問題。

NPC問題同時屬于NP hard問題，是NP與NPhard的交集。

總結(jié)

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

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