algorithm - 为什么考虑 NP 而不是 P？

Question

因式分解:给定一个整数 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) 是指数函数。