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

[dharma (達)]

看了許多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
推 yw1002      :Clay institute有這兩個問題
→ yw1002      :另外兩個:流體方程/Yang Mills 跟物理有關
→ yw1002      :超導的QMC numerical sign problem也是NP
→ yw1002      :看來好像可以一次作四個....
推 LPH66       :原 PO 可以搜尋 AKS 質因數判定演算法
→ LPH66       :是在這個結果出來之後才有質數判定在 P 的結論
→ LPH66       :(要判定一個數不是質數有比試除法還好的做法)
推 yw1002      :http://www.labviewpro.net/contest/about.php
→ yw1002      :去年第一關題目就是程式驗證質數