壹個NP－完全的問題具有如下性質：它可以在多項式時間內求解，當且僅當所有的其他的NP－完全問題也可以在多項式時間內求解。
P是所有可在多項式時間內用確定算法求解的判定問題的集合。NP是所有可在多項式時間內用不確定算法求解的判定問題的集合。
令L1和L2是兩個問題，如果有壹確定的多項式時間算法求解L1，而這個算法使用了壹個在多項式時間內求解L2的確定算法，則稱L1約化為L2。
如果可滿足性約化為壹個問題L，則稱L問題是NP-難度的。如果L是NP難度的且L（－NP，則稱L是NP－完全的。
NP並不是NON-POLYNOMIAL，把NP說成是NON-POLYNOMIAL，
是望文生義，讀書不求甚解。事實上，如果妳能夠證明某個
NP問題是個NON-POLYNOMIAL的問題，妳就可以去領那七個
百萬美元數學大獎中間的壹個了。
數學上著名的NP問題，完整的叫法是NP完全問題，也即
“NP COMPLETE”問題，簡單的寫法，是 NP=P？的問題。
問題就在這個問號上，到底是NP等於P，還是NP不等於P。
證明其中之壹，便可以拿百萬美元大獎。
這個獎還沒有人拿到，也就是說，NP問題到底是Polynomial，
還是Non-Polynomial，尚無定論。Mr. X信口開河敢說NP就是
Non-Polynomial，真是不知天高地厚，惹人笑話。
NP裏面的N，不是Non-Polynomial的N，是Non-Deterministic，
P代表Polynomial倒是對的。NP就是Non-deterministic Polynomial
的問題，也即是多項式復雜程度的非確定性問題。
什麽是非確定性問題呢？有些計算問題是確定性的，比如
加減乘除之類，妳只要按照公式推導，按部就班壹步步來，
就可以得到結果。但是，有些問題是無法按部就班直接地
計算出來。比如，找大質數的問題。有沒有壹個公式，妳
壹套公式，就可以壹步步推算出來，下壹個質數應該是多少
呢？這樣的公式是沒有的。再比如，大的合數分解質因數
的問題，有沒有壹個公式，把合數代進去，就直接可以算
出，它的因子各自是多少？也沒有這樣的公式。
這種問題的答案，是無法直接計算得到的，只能通過間接
的“猜算”來得到結果。這也就是非確定性問題。而這些
問題的通常有個算法，它不能直接告訴妳答案是什麽，但
可以告訴妳，某個可能的結果是正確的答案還是錯誤的。
這個可以告訴妳“猜算”的答案正確與否的算法，假如可以
在多項式時間內算出來，就叫做多項式非確定性問題。而
如果這個問題的所有可能答案，都是可以在多項式時間內
進行正確與否的驗算的話，就叫完全多項式非確定問題。
完全多項式非確定性問題可以用窮舉法得到答案，壹個個
檢驗下去，最終便能得到結果。但是這樣算法的復雜程度，
是指數關系，因此計算的時間隨問題的復雜程度成指數的
增長，很快便變得不可計算了。
人們發現，所有的完全多項式非確定性問題，都可以轉換
為壹類叫做滿足性問題的邏輯運算問題。既然這類問題的
所有可能答案，都可以在多項式時間內計算，人們於是就
猜想，是否這類問題，存在壹個確定性算法，可以在指數
時間內，直接算出或是搜尋出正確的答案呢？這就是著名
的NP=P？的猜想。
解決這個猜想，無非兩種可能，壹種是找到壹個這樣的算法，
只要針對某個特定NP完全問題找到壹個算法，所有這類問題
都可以迎刃而解了，因為他們可以轉化為同壹個問題。另外
的壹種可能，就是這樣的算法是不存在的。那麽就要從數學
理論上證明它為什麽不存在。
前段時間轟動世界的壹個數學成果，是幾個印度人提出了壹個
新算法，可以在多項式時間內，證明某個數是或者不是質數，
而在這之前，人們認為質數的證明，是個非多項式問題。
可見，有些看來好像是非多項式的問題，其實是多項式問題，
只是人們壹時還不知道它的多項式解而已。