PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 驗證某數是否為質數是NP問題

看板Prob_Solve (計算數學 Problem Solving)作者johnathan717 (好神公仔)時間10年前 (2014/06/01 11:52)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/4 (看更多)

※ 引述《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 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.230.127.136 ※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1401594745.A.E58.html ※ 編輯: johnathan717 (61.230.127.136), 06/01/2014 11:54:17