確定性多項式時間內(nèi)能夠解決的問題，解決某一類問題，如果肯定有一個上限，而且上限可以表示成一個確定性多項式的形式，當然無所謂說確定性多項式時間到底n的次數(shù)是多大了，只要不是隨著n呈現(xiàn)指數(shù)增長，那就是確定性多項式的問題，也就是一個p問題，如果不存在一個解決問題的多項式時間，那么就是一個np問題。

確定性指的是如果對于兩次解決同一個問題，得到的答案是相同的，那么就叫做確定性。否則叫做概率性。

確定性多項式時間內(nèi)能夠解決的問題還分為判定性問題或者是計算性問題。

概率性多項式時間是指并不是對于正確的結(jié)果我就能夠得到它是正確的，而是說正確的結(jié)果我們會以一定的概率得到我們的結(jié)果。什么叫做錯誤的結(jié)果呢：錯誤的結(jié)果就是這么兩個問題：一個是答案是對的，但是為什么圖靈機識別出來的它是錯的呢，另一個是答案是錯的，為什么圖靈機識別出來它是對的呢。這兩個情況各有概率來衡量。

之所以說這仍然是多項式時間算法是因為如果說對于上述兩種情況，只要我進行多次試驗，而且兩個概率都不是二分之一，那么多次試驗由大數(shù)定理判斷的話就應該能夠知道是什么情況，但是如果概率是二分之一，那么這種情況也區(qū)分不開到底哪個是對的，哪個是錯的。\

非確定性多項式時間問題，如果不存在一個問題總能夠在有限步驟內(nèi)解決，這就是一個非確定性多項式時間問題。這種問題一般都是隨著輸入的增大而變化的，如果輸入改變了那么解決問題的難度也就改變了。

對于一個問題p求解其復雜度的上下界比較容易確定，但是對于一個np問題，不能確定一個問題的下屆，只是有可能確定他的上屆。再者一個np完全問題，np完全問題指的是一類問題，在np完全問題當中的每個問題都可以相互轉(zhuǎn)化，一個問題解決了相當于所有的問題解決了，也稱之為npc問題。

總結(jié)

以上是生活随笔為你收集整理的确定性多项式时间的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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