※ 引述《dharma (達)》之銘言：
: 看了許多P和NP資料
: 怪怪的
: 例如下面這兩個例子
: 1.
: 判別一個數是否為質數是一個「P問題」
: 2.
: 不知81785036517是否為質數
: 但要確定277877是否為81785036517因數
: 可以直接拿去除
: 針對277877來驗證8178503651是否為質數的動作
: 可在多項式時間內完成
: 故針對某可能解來驗證某數是否為質數的問題
: 是一個NP問題
如果已經知道要驗證的是什麼數
那麼就可以deterministic在多項式時間完成，所以問題1是P
一個問題是NP的意思是說
你可以nondeterministic地在多項式時間驗證答案是"Yes"
例如要判斷一個數是不是合數，因為我可以nondeterministic猜出他的因數
再用多項式時間去驗證，所以這個問題可以很直觀的被證明是NP
至於判斷是不是質數的話，雖然沒那麼直觀，但也被證明是NP
甚至也有多項式時間保證正確的deterministic演算法，所以問題2其實也是P
http://en.wikipedia.org/wiki/AKS_primality_test
: 照道理說
: 一個大數a，要確認它是不是質數
: 應該遠比確認b是不是a的因數難很多
: 那麼
: 1.應該是「NP問題」
: 2.應該是「P問題」
: 我哪裡誤解了
: thanks
結論是兩個都是P