參考談談計算機中的NP，NP-Hard，NP完全以及"NP=P？"問題_哔哩哔哩_bilibili
目錄
一、計算機中的P問題、NP問題、NP-hard、NP-C問題
◼ 時間複雜度
◼ P問題
◼ NP問題
◼ NP-hard問題，NP-C問題
二、計算機中的"NP=P？"問題
一、計算機中的P問題、NP問題、NP-hard、NP-C問題
◼ 時間複雜度
時間複雜度定義為随着問題規模的增大，算法執行時間增長的快慢。它可以用來表示一個算法運作的時間效率。
上圖中，白色字部分的時間複雜度是多項式複雜度，黑色字部分的時間複雜度是非多項式複雜度，我們用經典計算機來實作這種算法時，花費時間會很多。
◼ P問題
通俗來說，p問題，就是可以在多項式時間内解決的問題。
算法要處理的資料是關于n的函數，比如有n個資料傳過來，我們要進行排序，如果排序的算法的時間複雜度是n的多項式，那麼就是一個p問題。
◼ NP問題
通俗來說，np問題，就是我們給你一個解，要驗證這個是否該問題的一個解，在驗證的過程中，如果我們能在n的多項式時間複雜度内驗證這個解是該問題的一個解， 那麼就是np問題。
比如說有一個party聚會，讓你從上萬人中找出所有好看的人，找出美女帥哥，那麼肯定要一個一個去周遊判斷，就很麻煩，很耗時間。但是如果反過來，我從上萬人中找出一個人，讓你判斷這個人好看不好看，這就很容易了，你看一眼就知道這個人好看不好看。
很顯然，p問題也是np問題。因為p問題可以在多項式時間内解決一個問題，那麼肯定也可以在多項式的時間内驗證一個解是否是該問題的解。
問題：那麼，np問題是不是p問題？
在講這個問題之前，我們先來了解什麼是NP-hard問題和NP-C問題。
◼ NP-hard問題，NP-C問題
那也就是說，NP-C問題就是最複雜的問題。有了這個思路，那麼我們假設如果NP-C問題能夠在多項式時間内解決的話，那麼所有的np問題就都能夠在多項式時間内解決，也就是所有的np問題都是p問題，那麼我們就可以證明p問題就是np問題。但是現在并沒有證明這個結論。
有哪些問題是np完全問題呢？
比如說邏輯電路問題，本身就是一個np問題。Hamilton問題就是給一個地圖，地圖上有很多城市， 我們選擇兩個城市作為起點和終點，路過一次且僅一次，到達終點。
旅行商問題：送貨員開着一輛貨車，從A城市出發，經過所有的城市，最後回到A，找出一條最短路徑。目前的想法是我把他經過所有的城市最後回到A的所有路線都枚舉出來，其實就是一個組合數學的全排列問題。假設一共有20個城市，A不用參與排列，那麼一共就是19！種可能，把所有的排列方法全都計算，找出最好的那條路線。
19！是一個非常大的資料，對傳統計算機來說非常耗時，不可接受。這就是一個np問題，而且是一個np完全問題。
二、計算機中的"NP=P？"問題
NP-C問題就是最複雜的問題。有了這個思路，那麼我們假設如果NP-C問題能夠在多項式時間内解決的話，那麼所有的np問題就都能夠在多項式時間内解決，也就是所有的np問題都是p問題，那麼我們就可以證明p問題就是np問題。但是現在并沒有證明這個結論。
現在大多數覺得np問題不等于p問題，因為np問題中存在着np完全問題，就像我們上文提到的邏輯電路問題，旅行商問題和Hamilton問題，想把這些問題在多項式時間内解決是不太可能的。
我們把它們歸納為一個集合時，分兩種情況：