轉(zhuǎn)載。

數(shù)學(xué)上著名的NP問題，完整的叫法是NP完全問題，也即“NP COMPLETE”問題，簡單的寫法，是 NP=P？的問題。問題就在這個問號上，到底是NP等於P，還是NP不等於P。證明其中之一，便可以拿百萬美元大獎。?

這個獎還沒有人拿到，也就是說，NP問題到底是Polynomial，還是Non-Polynomial，尚無定論。?

NP里面的N，不是Non-Polynomial的N，是Non-Deterministic，P代表Polynomial倒是對的。NP就是Non-deterministic Polynomial的問題，也即是多項式復(fù)雜程度的非確定性問題。?

什 么是非確定性問題呢？有些計算問題是確定性的，比如加減乘除之類，你只要按照公式推導(dǎo)，按部就班一步步來，就可以得到結(jié)果。但是，有些問題是無法按部就班 直接地計算出來。比如，找大質(zhì)數(shù)的問題。有沒有一個公式，你一套公式，就可以一步步推算出來，下一個質(zhì)數(shù)應(yīng)該是多少呢？這樣的公式是沒有的。再比如，大的 合數(shù)分解質(zhì)因數(shù)的問題，有沒有一個公式，把合數(shù)代進(jìn)去，就直接可以算出，它的因子各自是多少？也沒有這樣的公式。?

這種問題的答案，是 無法直接計算得到的，只能通過間接的“猜算”來得到結(jié)果。這也就是非確定性問題。而這些問題的通常有個算法，它不能直接告訴你答案是什么，但可以告訴你， 某個可能的結(jié)果是正確的答案還是錯誤的。這個可以告訴你“猜算”的答案正確與否的算法，假如可以在多項式時間內(nèi)算出來，就叫做多項式非確定性問題。而如果 這個問題的所有可能答案，都是可以在多項式時間內(nèi)進(jìn)行正確與否的驗算的話，就叫完全多項式非確定問題。?

完全多項式非確定性問題可以用窮舉法得到答案，一個個檢驗下去，最終便能得到結(jié)果。但是這樣算法的復(fù)雜程度，是指數(shù)關(guān)系，因此計算的時間隨問題的復(fù)雜程度成指數(shù)的增長，很快便變得不可計算了。?

人們發(fā)現(xiàn)，所有的完全多項式非確定性問題，都可以轉(zhuǎn)換為一類叫做滿足性問題的邏輯運算問題。既然這類問題的所有可能答案，都可以在多項式時間內(nèi)計算，人們於是就猜想，是否這類問題，存在一個確定性算法，可以在指數(shù)時間內(nèi)，直接算出或是搜尋出正確的答案呢？這就是著名的NP=P？的猜想。?

解決這個猜想，無非兩種可能，一種是找到一個這樣的算法，只要針對某個特定NP完全問題找到一個算法，所有這類問題都可以迎刃而解了，因為他們可以轉(zhuǎn)化為同一個問題。另外的一種可能，就是這樣的算法是不存在的。那么就要從數(shù)學(xué)理論上證明它為什么不存在。?

前段時間轟動世界的一個數(shù)學(xué)成果，是幾個印度人提出了一個新算法，可以在多項式時間內(nèi)，證明某個數(shù)是或者不是質(zhì)數(shù)，而在這之前，人們認(rèn)為質(zhì)數(shù)的證明，是個非多項式問題。可見，有些看來好象是非多項式的問題，其實是多項式問題，只是人們一時還不知道它的多項式解而已。

轉(zhuǎn)載于:https://www.cnblogs.com/yeahgis/archive/2012/03/23/2414294.html

總結(jié)

以上是生活随笔為你收集整理的NP=P?的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。