1、P問題

P是一個判定問題類,這些問題可以用一個確定性演算法在多項式時間內判定或解出。如果一個判定性問題的複雜度是該問題的一個例項的規模n的多項式函式，則我們說這種可以在多項式時間內解決的判定性問題屬於P類問題。P類問題就是所有複雜度為多項式時間的問題的集合。

NP是一個判定問題類,這些問題可以用一個確定演算法在多項式時間內檢查或驗證出它們的解;P事實上很直觀,我們通常在程式設計中求解的問題大多都是P類問題.比如說排序,找最短路徑等.

2、NP問題

然而有些問題很難找到多項式時間的演算法（或許根本不存在），比如找出無向圖中的哈米爾頓迴路問題，但是我們發現如果給了我們該問題的一個答案，我們可以在多項式時間內判斷這個答案是否正確。比如說對於哈米爾頓迴路問題，給一個任意的迴路，我們很容易判斷他是否是哈米爾頓迴路（只要看是不是所有的頂點都在迴路中就可以了）。這種可以在多項式時間內驗證一個解是否正確的問題稱為NP問題。顯然，所有的P類問題都是屬於NP問題的，但是現在的問題是，P是否等於NP?這個問題至今還未解決。

NP這個類事實上也很有趣,它並不要求給出一個演算法來求解問題本身,而只是要求給出一個確定性演算法在多項式時間內驗證它的解.

3、NP完全問題

此外請注意，NP問題不一定都是難解的問題，比如，簡單的陣列排序問題是P類問題，但是P屬於NP，所以也是NP問題，你能說他很難解麼？剛才說了，現在還不知道是否有P=NP或者PNP，但是後來人們發現還有一系列的特殊NP問題，這類問題的特殊性質使得很多人相信PNP，只不過現在還無法證明。這類特殊的NP問題就是NP完全問題（NPC問題，C代表complete）。

NP完全問題是求NP中判定問題的一個子類.NPC問題存在著一個令人驚訝的性質，即如果一個NPC問題存在多項式時間的演算法，則所有的NP問題都可以在多項式時間內求解，即P=NP成立！！這是因為，每一個NPC問題可以在多項式時間內轉化成任何一個NP問題。比如前面說的哈米爾頓迴路問題就是一個NPC問題。NPC問題的歷史並不久，cook在1971年找到了第一個NPC問題，此後人們又陸續發現很多NPC問題，現在可能已經有3000多個了。所以，我們一般認為NPC問題是難解的問題，因為他不太可能存在一個多項式時間的演算法（如果存在則所有的NP問題都存在多項式時間演算法，這太不可思議了，但是也不是不可能）。類似哈米爾頓迴路/路徑問題，貨郎擔問題，集團問題，最小邊覆蓋問題（注意和路徑覆蓋的區別），等等很多問題都是NPC問題，所以都是難解的問題。