The Dance of Disorder (Fluctuations of Entropy)

P問題(polynomial problems集合)是：在多項式時間內可以找出解的決策性問題(decision problem)的集合。
NP(未定多項式)問題(non-deterministic polynomial)：尚未找到多項式時間內的演算解法，但(若提供解，則)可以在多項式時間內驗證其解正確性的問題。因為仍未知這NP問題是否存在多項式時間內的演算法，故稱non-deterministic(未定)。
NP-complete問題是：屬於NP，而且是NP問題裡面最難解決的問題。
難到什麼程度？困難到只要其中某個問題可以在P時間內解決，那麼所有的NP問題就都可以在P時間內解決了。既然所有的NP問題都能歸約成NPC問題，那麼只要任意一個NPC問題找到了一個多項式的演算法，那麼所有的NP問題都能用這個演算法解決了，NP也就等於P 了。因此，給NPC找一個多項式演算法太不可思議了。【正是NPC問題的存在，使人們相信P≠NP】。我們可以就此直觀地理解，NPC問題目前沒有多項式的有效演算法，只能用指數級甚至階乘級複雜度的搜尋。
滿足以下兩個條件的，我們都稱之為NP-Complete
(一)「問題」是一個NP問題
(二)所有的NP問題都可以(用DTM)在polynomial time內規約成為這個「問題」。

Reducibility(可約性)
為了說明NPC問題，要先引入歸約(Reducibility)的概念。問題A可以歸約化為問題B，其含義為：可以用問題B的解法解答問題A，或說，問題A可以“隱含為”問題B。
“問題A可歸約化為問題B”重要的直觀意義是：B的時間複雜度高於或者等於A的時間複雜度。也就是說，問題A不比B難。這很容易理解。既然問題A能用問題B來解決，倘若B的時間複雜度比A的時間複雜度還低了，那A的演算法就可以改進為B的演算法，兩者的時間複雜度還是相同。
從可約性(reducibility)的定義中，我們看到，一個問題A約化為另一個問題B，時間複雜度增加了，問題的應用範圍也增大了。通過對某些問題的不斷約化，我們能夠不斷尋找複雜度更高，但應用範圍更廣的演算法來代替複雜度雖然低，但只能用於很小的一類問題的演算法。

回到前P和NP的問題，聯想起歸約化的遞移。自然地，我們會想問，如果不斷地約化上去，不斷找到能“通吃”若干小NP問題的一個稍複雜的大NP問題，那麼最後是否有可能找到一個時間複雜度最高，並且能“通吃”所有的 NP問題的這樣一個超級NP問題？答案(居然)是肯定的。也就是說，存在這樣一個NP問題，所有的NP問題都可以約化成它。換句話說，只要解決了這個問題，那麼所有的NP問題都解決了。這種問題的存在難以置信，並且更加不可思議的是，這種問題不只一個，它有很多個，它是一類問題。這一類問題就是NP-complete問題(NP-complete，可以隱含所有NP問題)。

NP-hard問題：如果所有的NP問題都能以多項式時間歸約至某問題，則稱該問題為NP-hard。(白話就是：NP中最難的那些問題)

【注意】

NP包含P和NP-complete, 因此NP集合中有簡單的問題和不容易快速得到解的難題。
NP hard不一定是NP。

因為NP-hard問題未必可以在多項式時間內驗證某個解之正確性（即不一定是NP問題）；
因此即使NP-complete問題有多項式時間的解（P=NP），NP hard依然可能沒有多項式時間的解。因此NP hard至少與NP-complete一樣難。

很顯然，所有的P類問題都是NP問題。也就是說，能多項式地解決一個問題，必然能多項式地驗證一個問題的解。既然正解都出來了，驗證任意給定的解也只需要比較一下就可以了。
困難的是想知道，是否所有的NP問題都是P類問題？。NP等不等於P?是一個電腦科學中知名的難題。

Euler diagram(from Wiki)

【多項式時間】
An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., T(n) = O(n^k) for some positive constant k. 

【時間複雜度】

P: 指有 Polynomial Time 解的問題。
NP:指還沒找到 Polynomial Time 解，也不確定是否有 Polynomial Time 解；但如果提供一個解，這個解可以在 Polynomial Time 被驗證的問題。can be verified "quickly"

NP Hard:指的也是還沒有找到 Polynomial Time 的解，但是不確定能否在 Polynomial Time 被驗證的問題。
NP Complete: 同時是NP也是NP-hard (a problem is NP-complete if it is both in NP and NP-hard)的問題。
The NP-complete problems represent the hardest problems in NP. If any NP-complete problem has a polynomial time algorithm, all problems in NP do.

所有的NP問題都可以用DTM在 polynomial time 內化約成為一個「問題」，這個「問題」就叫做NP-Hard Problem。
所以NP-Complete問題是NP-Hard 問題的一種特例，NP-Hard 問題可以不必是NP問題，譬如停機問題就是一個NP-Hard 問題但不是一個NP問題。

【例】旅行推銷員問題(TSP-travelling salesman problem)給定一系列城市和每對城市之間的距離，求解存取每一座城市一次並回到起始城市的最短迴路。TSP belongs to the class of combinatorial optimization problems known as NP-complete.

【例】背包問題(Knapsack problem)是一種組合最佳化的NP-complete問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內，我們如何選擇，才能使得物品的總價格最高。

(範例一)
假設我想要在一個有序的數列2,3,5,7,13,27中找到7的位置，最簡單的做法就是從第一個元素開始檢查起，如果不是元素7就再找下一個，直到找到為止，所以最差的情形就是我一路找直到了最後一個元素，如果數列有Ｎ個元素，我們最差的情形就是做了Ｎ次的比較，而每次做比較所花的時間是一個常數時間，因此這個演算法的上界將被 a×N 所界定，a為常數，所以這個演算法的時間複雜度為O(N)，

(範例二)

假設給予一組集合{−7,−3,−2,5,8}，然後問是否有一組子集合相加為0，怎麼做呢？最簡單的做法就是，窮舉出所有可能的子集合然後相加驗證是否剛好為0，假設集合中有Ｎ個元素，我會有2^N種的子集合，而且要加總最多Ｎ個元素，所以這個過程的時間複雜度為 O(N×(2^N))。

(範例三)NP-complete problem：圖同構(Wiki)問題

The Subgraph Isomorphism problem is NP-complete. The graph isomorphism problem is suspected to be neither in P nor NP-complete, though it is in NP. This is an example of a problem that is thought to be hard, but is not thought to be NP-complete.

The easiest way to prove that some new problem is NP-complete is first to prove that it is in NP, and then to reduce some known NP-complete problem to it. Therefore, it is useful to know a variety of NP-complete problems. The list below contains some well-known problems that are NP-complete when expressed as decision problems.

The list below contains some well-known problems that are NP-complete when expressed as decision problems.

(範例四)下圍棋，是NP-hard問題，但不是NP問題，我們要在一個殘局上找一個必勝下法，告訴我們下一步下在哪裡。
顯然，我們找不到這個解；而且，就算有人給我了一個解，我們也無法在P時間內判斷這個解是否正確。

【參考】

Wiki

ycc.idv.tw/algorithm-complexity-theory.html

https://bluelove1968.pixnet.net/blog/post/222283186

https://www.itread01.com/content/1548235989.html