数基在数值问题NP完备性证明中的作用

Question

我从tardos的算法设计书中读到关于NP完备性的内容，在证明子集和是NP完全一节中，它写道：

提出的子集和算法的运行时间为O(nW)。如果给定一个包含100个数字的实例，每个数字的长度都是100位，那么输入的数字只有100 * 100 = 10000位，但W大约是2^100。

我不明白这个说法，为什么W2^100？基数对这个问题有什么影响，我的意思是，如果我们把它改成其他的基数x，W会是x^100吗？如果我们把它改成一元基数呢？

谢谢。

Answer 1

要理解这一点，您需要考虑算法的运行时间是如何随着问题集中数字的增长而变化的。我假设你的教科书描述了通常对子集sum的动态编程攻击。该算法的运行时间随着问题集的宽度线性增长。(问题集宽度是集合中的正数减去负数的和。)此宽度随着集合中数字的 size 的增加而指数增长。例如，如果您使用101位数字而不是100位数字，则问题集的宽度会加倍。移动到102位数字，问题集宽度再次加倍。由于算法的运行时间随着问题集的宽度线性增长，因此每次运行时间也会加倍。随着输入大小的线性增长，这种倍增是运行时的指数增长，因此这不是一个多项式时间算法。

如果数字写在一个大于1的不同基数中，那么是的，您将看到该基数中的问题宽度呈指数增长。例如，在基数为10的情况下，添加另一个数字会使问题宽度增大十倍。如果您切换到一元，您将失去问题集大小的指数增长，但相反，任何给定问题的输入大小都比bases > 1中的输入大小指数大，因此您什么也得不到。