NP壹般指NP完全問題(NP-C問題)
是世界七大數學難題之壹。 NP的英文全稱是Non-deterministic Polynomial Complete的問題，即多項式復雜程度的非確定性問題。簡單的寫法是 NP=P？，問題就在這個問號上，到底是NP等於P，還是NP不等於P。
NP中的某些問題的復雜性與整個類的復雜性相關聯.這些問題中任何壹個如果存在多項式時間的算法,那麽所有NP問題都是多項式時間可解的.這些問題被稱為NP-完全問題(NPC問題)。
擴展資料：
NP完全問題舉例敘述
在壹個周六的晚上，妳參加了壹個盛大的晚會。由於感到局促不安，妳想知道這壹大廳中是否有妳已經認識的人。妳的主人向妳提議說，妳壹定認識那位正在甜點盤附近角落的女士羅絲。
不費壹秒鐘，妳就能向那裏掃視，並且發現妳的主人是正確的。然而，如果沒有這樣的暗示，妳就必須環顧整個大廳，壹個個地審視每壹個人，看是否有妳認識的人。
生成問題的壹個解通常比驗證壹個給定的解時間花費要多得多。這是這種壹般現象的壹個例子。與此類似的是，如果某人告訴妳，數13,717,421可以寫成兩個較小的數的乘積，妳可能不知道是否應該相信他，但是如果他告訴妳他可以因式分解為3607乘上3803，那麽妳就可以用壹個袖珍計算器容易驗證這是對的。
人們發現，所有的完全多項式非確定性問題，都可以轉換為壹類叫做滿足性問題的邏輯運算問題。既然這類問題的所有可能答案，都可以在多項式時間內計算，人們於是就猜想，是否這類問題，存在壹個確定性算法，可以在多項式時間內，直接算出或是搜尋出正確的答案呢？這就是著名的NP=P？的猜想。?
不管我們編寫程序是否靈巧，判定壹個答案是可以很快利用內部知識來驗證，還是沒有這樣的提示而需要花費大量時間來求解，被看作邏輯和計算機科學中最突出的問題之壹。它是斯蒂文·考克於1971年陳述的。