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

看板Math作者 (達)時間11年前 (2014/06/01 17:58), 11年前編輯推噓1(1推 0噓 4→)
留言5則, 2人參與, 最新討論串2/3 (看更多)
前面的推文回應有點難懂 要慢慢研究 現在先換個簡單的問法 A. 判別一個數是否為質數 B. 不知81785036517是否為質數 但要確定277877是否為81785036517因數 可以直接拿去除 照直覺說 一個大數a，要確認它是不是質數 應該遠比確認b是不是a的因數難很多 那麼 A應該比B困難啊 我哪裡誤解了 thanks -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.163.106.192 ※ 文章網址: http://www.ptt.cc/bbs/Math/M.1401616721.A.394.html
→
06/01 18:12, , 1F
你誤解維基百科的意思了，它的意思應該是找一個大數
06/01 18:12, 1F
→
06/01 18:12, , 2F
是不是質數有比用所有質數or所有數更好的辦法，所以
06/01 18:12, 2F
→
06/01 18:12, , 3F
是p問題，前面敘述的笨方法是np
06/01 18:12, 3F
推
06/02 06:11, , 4F
NP是"給你答案 可以很簡單確認答案是正確"的問題
06/02 06:11, 4F
→
06/02 06:12, , 5F
P是"不給你答案 可以很簡單自己找出答案"的問題
06/02 06:12, 5F
我好想有嚴重的理解誤會XD ※ 編輯: dharma (118.163.106.192), 06/02/2014 22:31:52
‣ 更多 dharma 的文章
文章代碼(AID): #1JYlbHEK (Math)
‣ 更多 dharma 的文章
文章代碼(AID): #1JYlbHEK (Math)