theory - SUBSET-SUM，解决方案数量的上限

Question

您可能知道，SUBSET-SUM 问题被定义为确定一组整数的子集的总和是否等于指定的整数。 (还有另一种子集和的定义，其中一组整数之和为零，但我们现在使用这个定义)

例如 ((1,2,4,5),6) 是 true 因为 (2,4) 求和 6。我们说 (2,4) 是一个“解决方案”

此外，((1,5,10),7) 是 false 因为参数中没有任何内容总和为 7

我的问题是，给定 SUBSET-SUM 的一组参数编号是否存在可能解决方案数量的多项式上限。在第一个示例中有 (2,4) 和 (1,5)。

我们知道，由于 SUBSET-SUM 是 NP 完全的，因此在 polynomail 时间中决定可能是不可能的。但是我的问题与决策时间无关，我严格询问解决方案列表的大小。

显然参数数的幂集的大小可以是解决方案列表大小的上限，但是它呈指数增长。我的直觉是应该存在多项式界限，但我无法证明这一点。

nb 我知道这听起来像是一道家庭作业题，但请相信我，这不是。我正在尝试自学 CS 理论的某些方面，这就是我的想法。

Answer 1

没有；取号:

(1, 2, 1+2, 4, 8, 4+8, 16, 32, 16+32, ..., 2²ⁿ, 2²ⁿ⁺¹, 2²ⁿ+2²ⁿ⁺¹)

并询问形成总和 1 + 2 + 4 + ... + 2²ⁿ + 2²ⁿ⁺¹。 (例如:n = 3 取集合 (1,2,3,4,8,12,16,32,48) 并询问总和为 63 的子集。)

您可以使用 1 和 2 或使用 1+2 形成 1+2。

您可以使用 4 和 8 或使用 4+8 组成 4+8。

....

你可以用 2²ⁿ 和 2²ⁿ⁺¹ 组成 2²ⁿ + 2²ⁿ⁺¹或 2²ⁿ+2²ⁿ⁺¹。

选择是独立的，所以至少有 3ⁿ=3^m/3，其中 m 是你的集合的大小。我敢打赌这可以得到显着加强，但这证明没有多项式界限。