※ 引述《dharma (达)》之铭言： : 看了许多P和NP资料 : 怪怪的 : 例如下面这两个例子 : 1. : 判别一个数是否为质数是一个「P问题」 : 2. : 不知81785036517是否为质数 : 但要确定277877是否为81785036517因数 : 可以直接拿去除 : 针对277877来验证8178503651是否为质数的动作 : 可在多项式时间内完成 : 故针对某可能解来验证某数是否为质数的问题 : 是一个NP问题 如果已经知道要验证的是什麽数 那麽就可以deterministic在多项式时间完成，所以问题1是P 一个问题是NP的意思是说 你可以nondeterministic地在多项式时间验证答案是"Yes" 例如要判断一个数是不是合数，因为我可以nondeterministic猜出他的因数 再用多项式时间去验证，所以这个问题可以很直观的被证明是NP 至於判断是不是质数的话，虽然没那麽直观，但也被证明是NP 甚至也有多项式时间保证正确的deterministic演算法，所以问题2其实也是P http://en.wikipedia.org/wiki/AKS_primality_test : 照道理说 : 一个大数a，要确认它是不是质数 : 应该远比确认b是不是a的因数难很多 : 那麽 : 1.应该是「NP问题」 : 2.应该是「P问题」 : 我哪里误解了 : thanks 结论是两个都是P --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 61.230.127.136 ※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1401594745.A.E58.html ※ 编辑: johnathan717 (61.230.127.136), 06/01/2014 11:54:17