作者dharma (达)
看板Prob_Solve
标题[问题] 验证某数是否为质数是NP问题
时间Sun Jun 1 10:54:05 2014
看了许多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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1401591248.A.A19.html
1F：→ freef1y3:P⊆NP，所以P问题一定是NP问题 06/01 11:05
2F：推 springman:验证的时间是 polynomial time 的问题就是 NP 问题。 06/01 15:35