作者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/cn.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