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

看板Math作者 (達)時間11年前 (2014/06/01 10:56), 編輯推噓3(3推 0噓 6→)
留言9則, 2人參與, 最新討論串1/3 (看更多)
看了許多P和NP資料 怪怪的 例如下面這兩個例子 1. 判別一個數是否為質數是一個「P問題」 2. 不知81785036517是否為質數 但要確定277877是否為81785036517因數 可以直接拿去除 針對277877來驗證8178503651是否為質數的動作 可在多項式時間內完成 故針對某可能解來驗證某數是否為質數的問題 是一個NP問題 照道理說 一個大數a，要確認它是不是質數 應該遠比確認b是不是a的因數難很多 那麼 1.應該是「NP問題」 2.應該是「P問題」 我哪裡誤解了 thanks -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.163.106.192 ※ 文章網址: http://www.ptt.cc/bbs/Math/M.1401591384.A.9A0.html
推
06/01 11:21, , 1F
Clay institute有這兩個問題
06/01 11:21, 1F
→
06/01 11:21, , 2F
另外兩個:流體方程/Yang Mills 跟物理有關
06/01 11:21, 2F
→
06/01 11:22, , 3F
超導的QMC numerical sign problem也是NP
06/01 11:22, 3F
→
06/01 11:22, , 4F
看來好像可以一次作四個....
06/01 11:22, 4F
推
06/01 12:04, , 5F
原 PO 可以搜尋 AKS 質因數判定演算法
06/01 12:04, 5F
→
06/01 12:05, , 6F
是在這個結果出來之後才有質數判定在 P 的結論
06/01 12:05, 6F
→
06/01 12:05, , 7F
(要判定一個數不是質數有比試除法還好的做法)
06/01 12:05, 7F
推
06/01 15:59, , 8F
06/01 15:59, 8F
→
06/01 15:59, , 9F
去年第一關題目就是程式驗證質數
06/01 15:59, 9F
‣ 更多 dharma 的文章
文章代碼(AID): #1JYfPOcW (Math)
‣ 更多 dharma 的文章
文章代碼(AID): #1JYfPOcW (Math)