※ 引述《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