什么是伪多项式时间？它与多项式时间有何不同？一些在伪多项式时间中运行的算法具有运行时间，如O(nW)(用于0/1背包问题)或O(√n)(用于试除法)；为什么这不算多项式时间？
要理解多项式时间和伪多项式时间之间的区别，我们需要从形式化什么"多项式时间"；方法
多项式时间的一般直觉是"；时间O(nk)对于一些k〃；例如，选择排序在时间O(n2)运行，这是多项式时间，而强力求解TSP需要时间O(n·n！)，这不是多项式时间。
这些运行时都引用了一些跟踪输入大小的变量n。例如，在选择排序中，n表示数组中元素的数量，而在TSP中，n指图中节点的数量。为了标准化"；n〃；实际上是指在这种情况下，时间复杂性的形式定义定义了"时间复杂性"；尺寸"；问题如下：
问题的输入大小是写出该输入所需的位数。
例如，如果排序算法的输入是32位整数的数组，则输入的大小将为32n，其中n是数组中的条目数。在具有n个节点和m条边的图中，输入可以指定为所有节点的列表，然后是所有边的列表，这将需要Ω(n+m)位。
给定这个定义，多项式时间的形式定义如下：
如果某个常数k的运行时间为O(xk)，则算法在多项式时间内运行，其中x表示给算法的输入位数。
当使用处理图形、列表、树等的算法时，此定义或多或少与传统定义一致。例如，假设您有一个排序算法，对32位整数的数组进行排序。如果使用类似选择排序的方法来执行此操作，则作为数组中输入元素数量的函数，运行时将为O(n2)。但是，输入数组中元素的数量n如何与输入的位数相对应？如前所述，输入的比特数将是x＝32n。因此，如果我们用x而不是n来表示算法的运行时间，我们得到运行时间是O(x2)，因此算法在多项式时间内运行。
类似地，假设你在图上进行深度优先搜索，这需要时间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(n3)内完成)。因此，该总体算法在时间O(n4)内运行，并且可能快得多。
2004年，三位计算机科学家发表了一篇名为PRIMES is In p的论文，给出了一个测试数字是否为素数的多项式时间算法。这被认为是一个具有里程碑意义的结果。那有什么大不了的？我们不是已经有了一个多项式时间算法，即上面的算法吗？
不幸的是，我们没有。请记住，时间复杂性的正式定义将算法的复杂性作为输入位数的函数我们的算法在时间O(n4)中运行，但作为输入位数的函数，这是什么？写出数字n需要O(logn)位。因此，如果我们让x是写出输入n所需的位数，则该算法的运行时间实际上是O(24x)，这是而不是x中的多项式。
这是多项式时间和伪多项式时间之间区别的核心。一方面，我们的算法是O(n4)，它看起来像一个多项式，但另一方面，在多项式时间的形式定义下，它不是多项式时间。
为了直观地了解为什么该算法不是多项式时间算法，请考虑以下内容。假设我想让算法做很多工作。如果我写出这样的输入：
10001010101011
则需要一些最坏情况下的时间，例如T才能完成。如果我现在在数字的末尾添加一个位，如下所示：
100010101010111
运行时现在(在最坏的情况下)将是2T。只要再加一位，我就可以把算法的工作量增加一倍！
如果运行时间是输入数值中的某个多项式，而不是表示它所需的位数，则算法在伪多项式时间中运行。我们的素数测试算法是伪多项式时间算法，因为它在时间O(n4)中运行，但它不是多项式时间算法，因为作为写出输入所需的位数x的函数，运行时间是O(24x)。"；PRIMES处于P〃；这篇论文的意义在于，它的运行时间(大致)是O(log12n)，它作为比特数的函数是O(x12])。
那么，为什么这很重要呢？我们有很多分解整数的伪多项式时间算法。然而，从技术上讲，这些算法是指数时间算法。这对密码学非常有用：如果你想使用RSA加密，你需要能够相信我们不能轻易地计算数字。通过将数字中的位数增加到一个巨大的值(比如1024位)，你可以使伪多项式时间因子分解算法必须花费的时间变得如此之大，以至于对数字进行因子分解是完全不可行的。另一方面，如果我们可以找到多项式时间因子分解算法，那么情况就不一定如此。添加更多的比特可能会导致工作量增长很多，但增长只是多项式增长，而不是指数增长。
也就是说，在许多情况下，伪多项式时间算法是非常好的，因为数字的大小不会太大。例如，计数排序具有运行时O(n+U)，其中U是数组中最大的数字。这是伪多项式时间(因为U的数值需要O(log U)位才能写出，所以运行时的输入大小是指数型的)。如果我们人为地约束U，使U不太大(比如说，如果我们让U为2)，那么运行时间是O(n)，这实际上是多项式时间。基数排序就是这样工作的：通过一次处理一位数字，每轮的运行时间是O(n)，因此总运行时间是0(n log U)。这实际上是多项式时间，因为写出n个数字进行排序使用Ω(n)位，并且log U的值与写出数组中最大值所需的位数成正比。
伪多项式时间复杂度是指输入值/大小为多项式，但输入大小为指数。
我们所说的大小是指写入输入所需的位数。
从背包的伪码中，我们可以发现时间复杂度为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在输入的长度上不是多项式，这就是它成为伪多项式的原因。
设s为表示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)其不是多项式。