我知道什么时候给定的算法可以称为伪多项式，但我在任何地方都找不到如何显示它相对于以位数给定的输入大小是指数的。我在这里的意思是正式证明输入大小的函数和时间复杂度之间的关系是指数的。也许基于背包问题来解释会比较容易。
是的，我读过这个帖子：什么是伪多项式时间？它与多项式时间有何不同？
但这不是我想要的。
提前感谢
(那是我最初的帖子，所以我很乐意详细说明！)
让我们以子集和问题为例。在这个问题中，我们想确定是否有一个由n个数字组成的集合s的子集加起来正好是W。有一个伪多项式时间DP算法在时间O(nW)中运行。让我们正式地证明，这是x的指数，输入的位数。
要做到这一点，我们需要考虑如何构建这个问题的输入。如果我们用通俗易懂的英语写出来，我们可以把S中的所有数字写成逗号分隔的列表，并在末尾加上W的值，以此来写下问题的输入。例如，我们可以通过编写来编写问题"是否存在{1,2,3,8,12}的子集，其总和为5？">
1,2,3,8,12,5
这是用十进制表示的。如果我们把数字写成二进制，我们就会得到
1,10,11,1000,1100,101
为了将整件事放入一个比特字符串中，我们需要以某种方式用分隔符对这些数字和逗号进行编码。要做到这一点，我们将使用一个标准的技巧。我们将所有数字的位数加倍，并将逗号替换为字符串01。在这种情况下，我们会得到
110111000111110111000000011111000001110011
我们可以通过读取大小为2的块来解码这个输入。每次我们读00，我们都知道它是0。每次我们读11，我们都知道它是1。每次我们读01，我们就知道我们已经读完了一个数字，应该从下一个开始。
那么这里需要多少比特呢？如果有n个数字，我们就有n个分隔符，需要2n个比特。如果数字本身总共有b位，我们需要2b的空间来存储它们。最后，我们需要lg W比特来写出二进制的W，所以我们需要2个lg W字节来写出W。这意味着比特总数，表示为x，满足
x=2(n+b+lg W)
现在看看我们算法的运行时，它是O(nW)。如果我们的输入集由数字1的n个副本组成，那么我们的输入的大小将是2(n+1+lgW)=2n+2+2lgW。如果我们现在选择W等于2n，那么输入的大小是2n+2+2n=4n+2。这意味着x=4n+2，因此n=Θ(x) 并且W＝2x=2Θ(x)。因此，如果算法的运行时间是O(nW)，则运行时间是0(x2Θ(x))，其在输入的大小上是指数的。
希望这能有所帮助！