我正在从 tardos 的算法设计书中阅读 NP 完整性，在证明子集总和是 NP 完全的部分，写到 -
为子集总和开发的算法的运行时间为 O(nW)。如果给出 100 个数字的实例，每个数字都是 100 位长，那么输入只有 100 * 100 = 10000 位，但 W 大约是 2^100。
我不明白这个说法，为什么是 W 2^100 ？base 对这个问题有什么影响，我的意思是，如果我们将其更改为其他 base x，W 会是 x^100 吗？如果我们将其更改为一元基数怎么办？
谢谢。
问问题
83 次
1 回答
0
要理解这一点，您需要考虑算法的运行时间如何随着问题集中数字大小的增长而变化。我假设您的教科书描述了对子集和的通常动态编程攻击。该算法的运行时间随着问题集的宽度线性增长。（问题集宽度是集合中正数之和减去负数之和。） 随着集合中数字大小的增加，该宽度呈指数增长。 例如，如果您使用 101 位数而不是 100 位数，则问题集的宽度会加倍. 移动到 102 位数字，问题集宽度再次加倍。而且由于算法的运行时间随着问题集的宽度线性增长，所以每次运行时间也会加倍。随着输入大小线性增长，这种加倍是运行时间的指数增长，因此这不是多项式时间算法。
如果数字写在不同的基数 > 1 中，那么是的，您会看到问题宽度在该基数中呈指数增长。例如，在以 10 为底的情况下，添加另一个数字会使问题宽度扩大十倍。如果您切换到一元，您将失去问题集大小的指数增长，但任何给定问题的输入大小都比它在基数 > 1 时的输入大小成倍大，因此您什么也得不到。
于 2012-01-04T00:38:07.163 回答