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

Question

什么是伪多项式时间？它与多项式时间有何不同？一些在伪多项式时间内运行的算法具有运行时，如O（nW）（用于0/1背包问题）或O(√n） （用于审判庭）；为什么不算作多项式时间？

Answer 1

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

我们所说的大小是指写入输入所需的位数。

从背包的伪码中，我们可以发现时间复杂度为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)

现在，背包的运行时间不是多项式。

Answer 2

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

多项式时间的常见直觉是“时间O（n^{k）对于某些k。”例如，选择排序在时间O（n2）中运行，这是多项式时间，而蛮力求解TSP需要时间O（n·n！），这不是多项式时间。}

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

问题输入的大小是写入该输入所需的位数。

例如，如果排序算法的输入是一个32位整数数组，那么输入的大小将是32n，其中n是数组中的条目数。在一个有n个节点和m条边的图中，输入可以指定为所有节点的列表，然后是所有边的列表，这需要Ω（n m）位。

根据该定义，多项式时间的形式定义如下：

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

当使用处理图形、列表、树等的算法时，这个定义或多或少与传统定义一致。例如，假设你有一个排序算法，对32位整数的数组进行排序。如果你使用类似选择排序这样的东西来做到这一点，运行时作为数组中元素进审量的函数，将是O（n²）。但是n，输入数组中元素的数量，如何对应于输入的位数？如前所述，输入的位数将是x=32n。因此，如果我们用x而不是n表示算法的运行时，我们得到运行时是O（x²），因此算法以多项式时间运行。

类似地，假设在图上进行深度优先搜索，这需要时间O（m n），其中m是图中的边数，n是节点数。这与给定输入的位数有什么关系？好的，如果我们假设输入指定为邻接列表（所有节点和边的列表），那么如前所述，输入位数将为x=Ω（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年，三位计算机科学家发表了一篇题为“素数在P中”的论文，提出了一种多项式时间算法来测试一个数是否为素数。这被认为是一个里程碑式的结果。那有什么大不了的？我们不是已经有了一个多项式时间算法吗，也就是上面的那个？

不幸的是，我们没有。记住，时间复杂度的形式定义讨论了算法的复杂度作为输入位数的函数。我们的算法在时间O（n^{4）内运行，但这是输入位数的函数吗？那么，写出数字n需要O（对数n）位。因此，如果我们让x是写出输入n所需的位数，则该算法的运行时间实际上是O（24x），这不是x中的多项式。}

这是多项式时间和伪多项式时间之间区别的核心。一方面，我们的算法是O（n^{4），它看起来像一个多项式，但另一方面，在多项式时间的形式定义下，它不是多项式时间。}

为了直观地了解该算法为什么不是多项式时间算法，请考虑以下几点。假设我想让算法做很多工作。如果我写出这样的输入：

10001010101011

然后需要一些最坏情况下的时间才能完成，例如T。如果我现在在数字的末尾添加一位，如下所示：

100010101010111

运行时现在（在最坏的情况下）是2T。我可以通过再增加一位来使算法的工作量翻倍！

如果运行时是输入数值中的某个多项式，而不是表示它所需的位数，则算法在伪多项式时间内运行。我们的主要测试算法是伪多项式时间算法，因为它在时间O（n^{4）中运行，但它不是多项式时间算法，因为作为写入输入所需位数x的函数，运行时间是O（24x）。“素数在P中”这篇论文之所以如此重要，是因为它的运行时间（大致）是O（log12n），它作为位数的函数是O（x12）。}

那么为什么这很重要呢？我们有很多伪多项式时间算法来分解整数。然而，从技术上讲，这些算法是指数时间算法。这对于密码学非常有用：如果你想使用RSA加密，你需要能够相信我们不能轻松地计算数字。通过将数字中的位数增加到一个巨大的值（例如1024位），可以使伪多项式时间分解算法必须花费的时间量变得如此之大，以至于完全不可能对数字进行因子分解。另一方面，如果我们可以找到多项式时间因子分解算法，则不一定是这样。添加更多位可能会导致工作量大幅增加，但增长将仅为多项式增长，而不是指数增长。

也就是说，在许多情况下，伪多项式时间算法非常好，因为数字的大小不会太大。例如，计数排序的运行时为O（n U），其中U是数组中最大的数字。这是伪多项式时间（因为U的数值需要O（log U）位才能写出，所以运行时在输入大小中是指数级的）。如果我们人为地限制U，使U不会太大（例如，如果我们让U为2），那么运行时为O（n），实际上是多项式时间。这就是基数排序的工作原理：通过一次一位地处理数字，每轮的运行时间是O（n），所以总体运行时间是O（n log U）。这实际上是多项式时间，因为写出n个数字进行排序使用Ω（n）位，而log U的值与写出数组中最大值所需的位数成正比。

希望这有帮助！