阶乘时间算法和P / NP [英] Factorial-time algorithms and P/NP

问题描述

很容易看到n！ N幂的增长速度几乎比几乎任何东西都慢（例如100 ^ N），因此，如果一个问题被认为是NP完全的并且一个问题发生在n上！一种近似解决方案的算法，有人会做史努比舞。

It's quite easy to see that n! grows slower than almost anything to the N power (say, 100^N) and so, if a problems is considered NP complete and one happened upon a n! algorithm that approximates the solution, one would do the Snoopy dance.

关于这种情况，我有两个问题：

I have 2 questions about this situation:

1. 将n！算法被认为是多项式时间的解决方案？阶乘肯定不是一个幂的名词。


2. 如果找到n！解决方案意味着我们有一个相当快的算法，因为n！增长速度快于2 ^ N，那么这是否意味着某些NP完全问题不需要启发式/近似算法（模糊情况除外）？

当然，这两个问题取决于第一段为真；

Of course, these two questions rely on the first paragraph being true; if I've erred, please let me know.

推荐答案

1. 否。阶乘时间不是多项式时间。多项式时间通常表示O（N ^k ）形式的方程，其中N =要处理的项目数，k =某个常数。重要的是，指数是一个常数-您是将N本身乘以一定数量的固定值-并不依赖于N本身。阶乘复杂度算法意味着乘法的数量不是固定的-乘法的数量本身随N增长。

1. No. factorial time is not polynomial time. Polynomial time normally means an equation of the form O(N^k), where N = number of items being processed, and k = some constant. The important part is that the exponent is a constant -- you're multiplying N by itself some number of that's fixed -- not dependent on N itself. A factorial-complexity algorithm means the number of multiplications is not fixed -- the number of multiplications itself grows with N.

您似乎在这里有同样的问题。 N ² 将是多项式复杂度。 2 ^N 不会。您的基本信条也是错误的-至少作为一般规则，阶乘复杂性算法不是并不意味着我们有一个相当快的算法。如果有的话，得出的结论则相反：因数算法在一些特殊情况下（例如，N极小）可能是可行的，但是随着N的增长，非常很快变得不切实际。

You seem to have the same problem here. N² would be polynomial complexity. 2^N would not be. Your basic precept is mistaken as well -- a factorial-complexity algorithm does not mean "we have a decently fast algorithm", at least as a general rule. If anything, the conclusion is rather the opposite: a factorial algorithm may be practical in a few special cases (i.e., where N is extremely small) but becomes impractical very quickly as N grows.

让我们尝试将其视为正确的观点。二进制搜索为O（log N）。线性搜索为O（N）。在排序中，慢速算法为O（N ² ），而高级算法为O（N lg N）。阶乘复杂度（显然足够）为O（N！）。

Let's try to put this in perspective. A binary search is O(log N). A linear search is O(N). In sorting, the "slow" algorithms are O(N²), and the "advanced" algorithms O(N lg N). A factorial-complexity is (obviously enough) O(N!).

让我们尝试为此添加一些数字，考虑到目前（仅）10个项目。其中每一个大约是10个项目而不是1个项目需要花费更长的时间：

Let's try to put some numbers to that, considering (for the moment) only 10 items. Each of these will be roughly how many times longer processing should take for 10 items instead of 1 item:

O（log N）：2

O（N）：10

O（N log N）：23

O（N ² ）：100

O （N！）：3,628,800

O(log N): 2
O(N):10
O(N log N): 23
O(N²): 100
O(N!): 3,628,800

目前，我已经作弊了一点，并使用自然对数代替了以2为底的对数，但我们只是在尝试估计（在任何情况下，差异都是一个很小的常数因子）。

For the moment I've cheated a bit, and use a natural logarithm instead of a base 2 logarithm, but we're only trying for ballpark estimates here (and the difference is a fairly small constant factor in any case).

如您所见，阶乘复杂度算法的增长率为

As you can see, the growth rate for the factorial-complexity algorithm is much faster than for any of the others. If we extend it to 20 items, the difference becomes even more dramatic:

O（log N）：3

O（n）：20

O（N log N）：60

O（N ² ）：400

O（N！）：2,432,902,008,176,640,000

O(log N): 3
O(n): 20
O(N log N): 60
O(N²): 400
O(N!): 2,432,902,008,176,640,000

N的增长率！速度如此之快，几乎可以保证它们是不切实际的，除非已知非常少。对于笑容，我们假设上述流程的基本操作可以在单个机器时钟周期内运行。为了便于讨论（为了简化计算），我们假设使用10 GHz CPU。因此，基础是处理一项需要0.1 ns。在这种情况下，有20个项目：

The growth rate for N! is so fast that they're pretty much guaranteed to be impractical except when the number of items involves is known to be quite small. For grins, let's assume that the basic operations for the processes above can each run in a single machine clock cycle. Just for the sake of argument (and to keep the calculations simple) let's assume a 10 GHz CPU. So, the base is that processing one item takes .1 ns. In that case, with 20 items:

O（log N）= .3 ns

O（N）= 2 ns

O（N log N）= 6 ns

O（N ² ）= 40 ns

O（N！）= 7.7年。

O(log N) = .3 ns
O(N) = 2 ns
O(N log N) = 6 ns
O(N²) = 40 ns
O(N!) = 7.7 years.

这篇关于阶乘时间算法和P / NP的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！