它是世界七大數學難題之壹。NP的英文全稱是非確定性多項式完備的問題，即多項式復雜度的不確定性。簡單的寫法就是NP=P？問題就在這個問號上，NP等於P還是NP不等於P。
有些NP問題的復雜程度與整個類的復雜程度有關。如果這些問題中的任何壹個都有多項式時間的算法，那麽所有的NP問題都是多項式時間可解的。這些問題被稱為NP完全問題(NPC問題)。
擴展數據:
NP完全問題的例子
在壹個星期六的晚上，妳參加了壹個盛大的聚會。很尷尬，妳想知道這個大廳裏有沒有妳已經認識的人。妳的主人建議妳壹定要認識坐在靠近甜點盤角落裏的羅斯女士。
妳不需要壹秒鐘就能掃壹眼那裏，發現妳的主人是對的。但是，如果沒有這樣的暗示，妳必須環視整個大廳，壹個壹個地看每個人，看看有沒有妳認識的人。
生成問題的解決方案通常比驗證給定的解決方案花費更多的時間。這是這種普遍現象的壹個例子。同樣，如果有人告訴妳，13，717，421這幾個數字可以寫成兩個更小的數的乘積，妳可能不知道該不該相信他，但如果他告訴妳，他可以因式分解成3607乘以3803，那麽妳就可以用袖珍計算器很容易地驗證這壹點。
發現所有完全多項式不確定性問題都可以轉化為壹類稱為滿足問題的邏輯運算問題。由於這類問題所有可能的答案都可以在多項式時間內計算出來，所以人們想知道是否存在這類問題的確定性算法，可以在多項式時間內直接計算或搜索出正確答案。這就是著名的NP=P？猜猜看。？
無論我們是否熟練地編寫了壹個程序，確定壹個答案是否可以用內部知識快速驗證，或者在沒有這種提示的情況下需要花費大量時間來解決，這被視為邏輯和計算機科學中最突出的問題之壹。它是由史蒂文·科克在1971中陳述的。