为什么要考虑NP,而不是P？

Question

因子:Gven是一个整数N,找到整数1 <a,b <N,如果它们存在则N = ab,否则说N是素数.

我知道素数测试是在P中,但为什么不考虑因素？

这是我的算法:

For each a = 1 ... sqrt(N)
    if(N % a == 0)
        b = N/a
        add (a,b) to the result
    Endif
EndFor

它以O(sqrt(N))运行.

Answer 1

单个数值的输入大小由其二进制表示的长度来度量.确切地说,输入数值的大小与... n成比例log_2(n).因此,您的算法在指数时间内运行.

例如,假设我们N使用您的算法计算一个数字.如果N是素数,你必须测试至少sqrt(N)因素.(或者,您可以为此计算素数表,但它仍然不是线性的).

无论如何,你测试sqrt(N)时间.但问题的大小定义为S=log2(N).所以我们有N=2^S.因此它是一个sqrt(2^S)=2^(S/2)具有指数意义的.