概念1:
在計算機學科中，存在多項式時間的算法的壹類問題，稱之為P類問題；而像梵塔問題、推銷員旅行問題、（命題表達式）可滿足問題這類，至今沒有找到多項式時間算法解的壹類問題，稱之為NP類問題。
概念2:
多項式時間（Polynomial time）在計算復雜度理論中，指的是壹個問題的計算時間m(n)不大於問題大小n的多項式倍數。任何抽象機器都擁有壹復雜度類，此類包括可於此機器以多項式時間求解的問題。
以數學描述的話，則可說m(n) = O(n)，此n為壹常數值（依問題而定）
拿推銷員旅行問題為例，假設推銷員亨利有向6個城市推銷公司產品的任務，並規定了壹個旅行預算。他手中有壹張航班票價表，他要從A城開始走遍圖中的6個城市後返回A城，並且不超出預算，請妳幫他找出應走的路線。如果給出的預算寬裕，則任務很簡單；如果預算比較緊張，妳就得認真設計路線了。妳得考慮每壹種可能的次序，以使旅費最少。
而NP問題中最困難的問題稱之為NP完全問題(NP-complete)，已經證明的包括：電話網絡的最優幾何設計、格子棋的最佳走法。根據庫克定理，任意壹個NP完全問題如果能夠在多項式時間內解決，則所有的NP問題都能在多項式時間內解決，而至今這壹問題仍無答案。
什麽是非確定性問題呢？有些計算問題是確定性的，比如加減乘除之類，妳只要按照公式推導，按部就班壹步步來，就可以得到結果。但是，有些問題是無法按部就班直接地計算出。比如，找大質數的問題。有沒有壹個公式，妳壹套公式，就可以壹步步推算出來，下壹個質數應該是多少呢？這樣的公式是沒有的。再比如，大的合數分解質因數的問題，有沒有壹個公式，把合數代進去，就直接可以算出，它的因子各自是多少？也沒有這樣的公式。
這種問題的答案，是無法直接計算得到的，只能通過間接的“猜算”來得到結果。這也就是非確定性問題。而這些問題的通常有個算法，它不能直接告訴妳答案是什麽，但可以告訴妳，某個可能的結果是正確的答案還是錯誤的。這個可以告訴妳“猜算”的答案正確與否的算法，假如可以在多項式時間（多項式時間： 運行時間最多是輸入量的多項式函數）內算出來，就叫做多項式非確定性問題。而如果這個問題的所有可能答案，都是可以在多項式時間內進行正確與否的驗算的話，就叫完全多項式非確定問題。
完全多項式非確定性問題可以用窮舉法得到答案，壹個個檢驗下去，最終便能得到結果。但是這樣算法的復雜程度，是指數關系，因此計算的時間隨問題的復雜程度成指數的增長，很快便變得不可計算了。人們發現，所有的完全多項式非確定性問題，都可以轉換為壹類叫做滿足性問題的邏輯運算問題。既然這類問題的所有可能答案，都可以在多項式時間內計算，人們於是就猜想，是否這類問題，存在壹個確定性算法，可以在指數時間內，直接算出或是搜尋出正確的答案呢？這就是著名的NP=P？的猜想。
解決這個猜想，無非兩種可能，壹種是找到壹個這樣的算法，只要針對某個特定NP完全問題找到壹個算法，所有這類問題都可以迎刃而解了，因為他們可以轉化為同壹個問題。另外的壹種可能，就是這樣的算法是不存在的。那麽就要從數學理論上證明它為什麽不存在。
前段時間轟動世界的壹個數學成果，是幾個印度人提出了壹個新算法，可以在多項式時間內，證明某個數是或者不是質數，而在這之前，人們認為質數的證明，是個非多項式問題。可見，有些看來好象是非多項式的問題，其實是多項式問題，只是人們壹時還不知道它的多項式解而已。
什麽叫做NP問題，什麽叫做NPC問題?
首先說明壹下問題的復雜性和算法的復雜性的區別，下面只考慮時間復雜性。算法的復雜性是指解決問題的壹個具體的算法的執行時間，這是算法的性質；問題的復雜性是指這個問題本身的復雜程度，是問題的性質。比如對於排序問題，如果我們只能通過元素間的相互比較來確定元素間的相互位置，而沒有其他的附加可用信息，則排序問題的復雜性是O(nlgn)，但是排序算法有很多，冒泡法是O(n^2)，快速排序平均情況下是O(nlgn)等等，排序問題的復雜性是指在所有的解決該問題的算法中最好算法的復雜性。問題的復雜性不可能通過枚舉各種可能算法來得到，壹般都是預先估計壹個值，然後從理論上證明。
為了研究問題的復雜性，我們必須將問題抽象，為了簡化問題，我們只考慮壹類簡單的問題，判定性問題，即提出壹個問題，只需要回答yes或者no的問題。任何壹般的最優化問題都可以轉化為壹系列判定性問題，比如求圖中從A到B的最短路徑，可以轉化成：從A到B是否有長度為1的路徑？從A到B是否有長度為2的路徑？。。。從A到B是否有長度為k的路徑？如果問到了k的時候回答了yes，則停止發問，我們可以說從A到B的最短路徑就是k。
如果壹個判定性問題的復雜度是該問題的壹個實例的規模n的多項式函數，則我們說這種可以在多項式時間內解決的判定性問題屬於P類問題。P類問題就是所有復雜度為多項式時間的問題的集合。
然而有些問題很難找到多項式時間的算法（或許根本不存在），比如找出無向圖中的哈米爾頓回路問題，但是我們發現如果給了我們該問題的壹個答案，我們可以在多項式時間內判斷這個答案是否正確。比如說對於哈米爾頓回路問題，給壹個任意的回路，我們很容易判斷他是否是哈米爾頓回路（只要看是不是所有的頂點都在回路中就可以了）。這種可以在多項式時間內驗證壹個解是否正確的問題稱為NP問題。顯然，所有的P類問題都是屬於NP問題的，但是現在的問題是，P是否等於NP?這個問題至今還未解決。註意，NP問題不壹定都是難解的問題，比如簡單的數組排序問題是P類問題，但是P屬於NP，所以也是NP問題，妳能說他很難解麽？ 剛才說了，現在還不知道是否有P=NP或者P<>NP，但是後來人們發現還有壹系列的特殊NP問題，這類問題的特殊性質使得很多人相信P<>NP，只不過現在還無法證明。這類特殊的NP問題就是NP完全問題（NPC問題，C代表complete）。NPC問題存在著壹個令人驚訝的性質，即如果壹個NPC問題存在多項式時間的算法，則所有的NP問題都可以在多項式時間內求解，即P=NP成立！！這是因為，每壹個NPC問題可以在多項式時間內轉化成任何壹個NP問題。比如前面說的哈米爾頓回路問題就是壹個NPC問題。NPC問題的歷史並不久，cook在1971年找到了第壹個NPC問題，此後人們又陸續發現很多NPC問題，現在可能已經有3000多個了。所以，我們壹般認為NPC問題是難解的問題，因為他不太可能存在壹個多項式時間的算法（如果存在則所有的NP問題都存在多項式時間算法，這太不可思議了，但是也不是不可能）。
類似哈米爾頓回路/路徑問題，貨郎擔問題，集團問題，最小邊覆蓋問題（註意和路徑覆蓋的區別），等等很多問題都是NPC問題，所以都是難解的問題。