什么是伪多项式时间? 它与多项式时间有什么不同？

为了理解多项式时间和伪多项式时间之间的区别，我们需要从形式化“多项式时间”的含义开始。

多项式时间的一般直觉是“时间 O (n^K)对于某个 k”。例如，选择排序在时间 O (n²)中运行，这是多项式时间，而蛮力求解 TSP需要时间 O (n & middot; n!)不是多项式时间。

这些运行时都引用一些跟踪输入大小的变量 n。例如，在选择排序中，n 表示数组中元素的数量，而在 TSP 中，n 表示图中节点的数量。为了标准化“ n”在这个上下文中的实际含义，时间复杂性的正式定义将问题的“大小”定义如下:

The size of the input to a problem is the number of bits required to write out that input.

例如，如果一个排序算法的输入是一个由32位整数组成的数组，那么输入的大小就是32n，其中 n 是数组中的条目数。在一个有 n 个节点和 m 条边的图中，输入可能被指定为一个所有节点的列表，后面跟着一个所有边的列表，这将需要 & Omega; (n + m)位。

根据这个定义，多项式时间的形式定义如下:

如果一个算法的运行时间对于某个常数 k 为 O (x^K) ，则该算法在多项式时间内运行，其中 x 表示给该算法的输入位数。

当使用处理图形、列表、树等的算法时，这个定义或多或少与传统定义相一致。例如，假设你有一个对32位整数数组进行排序的排序算法。如果使用诸如选择排序之类的方法来执行此操作，则作为数组中输入元素数目的函数，运行时将为 O (n²)。但是 n，输入数组中的元素数，是如何与输入的位数对应的呢？如前所述，输入的位数为 x = 32n。因此，如果我们用 x 而不是 n 来表示算法的运行时间，我们得到运行时间是 O (x²) ，所以算法在多项式时间内运行。

类似地，假设对一个图执行 depth-first search，这需要花费时间 O (m + n) ，其中 m 是图中的边数，n 是节点数。这与输入的位数有什么关系？好的，如果我们假设输入被指定为一个邻接列表(一个包含所有节点和边的列表) ，那么如前所述，输入位的数目将是 x = & Omega; (m + n)。因此，运行时将是 O (x) ，所以算法在多项式时间内运行。

然而，当我们开始讨论对数字进行操作的算法时，事情就不那么顺利了。让我们考虑一下测试一个数字是否为素数的问题。给定一个数字 n，您可以使用以下算法测试 n 是否为素数:

function isPrime(n):
for i from 2 to n - 1:
if (n mod i) = 0, return false
return true

那么这段代码的时间复杂度是多少呢？内部循环运行 O (n)次，每次做一些工作来计算 n mod i (作为一个非常保守的上界，这当然可以在时间 O (n³)中完成)。因此，这个整体算法在时间 O (n⁴)中运行，而且可能要快得多。

2004年，三位计算机科学家发表了一篇名为 PRIMES 在 P 的论文，给出了一个多项式时间算法来测试一个数字是否为素数。这被认为是一个里程碑式的结果。有什么大不了的？我们不是已经有一个多项式时间算法了吗，也就是上面的那个？

不幸的是，我们没有。请记住，时间复杂度的正式定义讨论了算法 作为输入位数的函数的复杂度，我们的算法在时间 O (n⁴)中运行，但是输入位数的函数是什么呢？写出 n 需要 O (log n)位。因此，如果我们让 x 表示写出输入 n 所需的位数，那么这个算法的运行时间实际上是 O (2^4倍) ，即 没有是 x 中的一个多项式。

这是区分多项式时间和伪多项式时间的核心。一方面，我们的算法是 O (n⁴) ，它看起来像一个多项式，但另一方面，在多项式时间的形式定义下，它不是多项式时间。

To get an intuition for why the algorithm isn't a polynomial-time algorithm, think about the following. Suppose I want the algorithm to have to do a lot of work. If I write out an input like this:

10001010101011

那么它将需要一些最坏的情况下的时间，比如说 T，来完成。如果我现在把 一点点加到数字的末尾，像这样:

1000101010111

运行时现在(在最坏的情况下)是2T。我可以加倍的工作量的算法只需要增加一位！

如果运行时是某个多项式 在输入的数值中，则算法在 伪多项式时间伪多项式时间中运行，而不是在表示它所需的位数中运行。我们的素数测试算法是一个伪多项式时间算法，因为它在时间 O (n⁴)中运行，但它不是一个多项式时间算法，因为作为写出输入所需位 x 的函数，运行时间是 O (2^4倍)。“ PRIMES 在 P 中”文件之所以如此重要，是因为它的运行时(大致)是 O (log¹²n) ，这是位数为 O (x¹²)的函数。

那么这有什么关系呢？对于整数分解，我们有很多伪多项式时间算法。然而，从技术上讲，这些算法是指数时间算法。这对于加密非常有用: 如果你想使用 RSA 加密，你需要能够相信我们不能简单地分解数字。通过将数字中的比特数增加到一个巨大的数值(比如说1024比特) ，你可以让伪多项式时间分解算法所花费的时间变得如此巨大，以至于对这些数字进行分解是完全不可行的。另一方面，如果我们可以找到一个 多项式时间分解算法，情况就不一定是这样了。添加更多的比特可能会导致工作量大幅增长，但增长只是多项式增长，而不是指数增长增长。

也就是说，在许多情况下，伪多项式时间算法是完全没问题的，因为这些数字的大小不会太大。例如，计数排序具有运行时 O (n + U) ，其中 U 是数组中最大的数字。这是伪多项式时间(因为 U 的数值需要 O (log U)比特来写出，所以运行时的输入大小是指数级的)。如果我们人为地约束 U，使 U 不太大(例如，如果我们让 U 是2) ，那么运行时是 O (n) ，实际上是多项式时间。这就是 基数排序基数排序的工作原理: 通过一次处理一个数字，每轮的运行时是 O (n) ，所以整个运行时是 O (n log U)。这实际上是 是多项式时间，因为写出 n 个数字排序使用 & Omega; (n)位，而 log U 的值与写出数组中最大值所需的位数成正比。

Hope this helps!

伪多项式时间复杂度指输入的值/大小为多项式，但输入的大小为指数式。

By size we mean the number of bits required to write the input.

From the pseudo-code of knapsack, we can find the time complexity to be O(nW).

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n) //
Knapsack capacity (W)
for w from 0 to W
do   m[0, w] := 0
end for
for i from 1 to n do
for j from 0 to W do
if j >= w[i] then
m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
else
m[i, j] := m[i-1, j]
end if
end for
end for

在这里，W 在输入的长度上不是多项式，这就是为什么它是伪多项式的原因。

设表示 W 所需的位数

i.e. size of input= s =log(W) (log= log base 2)
-> 2^(s)=2^(log(W))
-> 2^(s)=W  (because  2^(log(x)) = x)

现在，running time of knapsack = O (nW) = O (n * 2 ^ s) 这不是多项式。