是多項式複雜程度的非確定性問題。
簡單的寫法就是“NP=P？”。
問題也就在這個問號上面。
到底是NP等於P，還是NP不等於P。
當然，幾乎絕大多數的人，都希望NP等於P。
因為這背後的實際意義，太過重大。
只可惜，就算再多人的希望，也不能將這道千禧年大獎難題，給變成事實。
它仍舊在等待著，能夠解決它的人出現。
“P類問題和NP類問題的關係……”
第一篇文獻結束，陳舟看了看草稿紙上，自己所寫的內容，小聲的呢喃了一句。
事實上，要知道“NP=P”是個什麼問題，先要知道什麼是P類問題，什麼是NP類問題。
P類問題和NP類問題這兩個概念，是和計算理論中的時間複雜度有關的。
至於計算理論中的時間複雜度，簡單來說，就是解決一個問題的某種演算法，所需要的計算量，隨著這個問題的規模增長而增長的速度。
這個概念，更多的被應用在資訊學的計算機演算法上。
在演算法中，時間複雜度本質上，是指計算量增長的速度，而不是這個演算法執行的時間。
自然的，對於同樣的一個問題。
如果採用不同的演算法，其時間複雜度也是不一定相同的。
而如果某個問題，能夠找到的最優演算法的時間複雜度，是n的多項式函式。
那麼，這個問題就被稱之為P類問題。
P也就是多項式的英文首字母。
此外，還有一些問題，無論其是否能夠在多項式時間複雜度內求解，如果知道一個隨便給出的可能解，能夠在多項式時間複雜度內驗證其是否為所求的解。
那麼，這類問題就被稱之為NP類問題。
至於為什麼要研究一個問題，是否有多項式時間複雜度的演算法。
則是因為，多項式時間複雜度的計算量增長速度，有些過於“快”了。
隨著n的增大，其計算量遠遠小於O(2^n、O(n！、O(n^n這些時間複雜度問題。
就好比那個很有名的大整數質因數分解問題。
給出一個2048位的二進位制整數，要找出它的某個質因數。
一般來說，可能舉全世界的計算能力，也需要上百年的時間，才能完成這個求解計算過程。
但是，如果知道某一個質數的話。
卻可以用最普通的計算機，在幾秒鐘時間內，確定這個質數，是不是這個2048位二進位制整數的一個因數。
而這，便是不同時間複雜度，在實際計算過程中的差別！
雖說有時候快了不好，可是在時間複雜度上，還是快一點比較有應用價值。
自然的，全部的P類問題，都屬於NP類問題。