作者dharma (達)
看板Prob_Solve
標題Re: [問題] 驗證某數是否為質數是NP問題
時間Sun Jun 1 18:01:09 2014
前面大家的回應有點難懂
要慢慢研究
現在先換個簡單的問法
A.
判別一個數是否為質數
B.
不知81785036517是否為質數
但要確定277877是否為81785036517因數
可以直接拿去除
照直覺說
一個大數a，要確認它是不是質數
應該遠比確認b是不是a的因數難很多
那麼
A應該比B困難啊
我哪裡誤解了
thanks
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.163.106.192
※ 文章網址: http://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1401616872.A.4B6.html
1F：推 Fenikso:"難不夠多" 就這樣 XD 06/01 19:11
2F：→ freef1y3:乘法也比加法難，但兩個都是P 06/01 20:52
3F：→ stimim:我覺得你可能看錯 B 命題了，可以給來源嗎？ 06/01 21:26
http://ppt.cc/teLf
※ 編輯: dharma (118.163.106.192), 06/03/2014 13:39:47
4F：推 stimim:他的敘述很奇怪,英文版的比較好,判斷一個數字是合數是NP 06/03 23:03
5F：→ stimim:因為一個數字如果是合數，你可以找到一個證據，並在P的時間 06/03 23:03
6F：→ stimim:內驗證 06/03 23:04