您可能知道，SUBSET-SUM问题被定义为确定一组整数的子集是否与指定的整数相加。（还有另一个子集和定义，其中一组整数和为零，但我们现在使用这个定义）
例如((1,2,4,5),6)是true因为(2,4)总和6。我们说这(2,4)是一个"solution"
此外，((1,5,10),7)是false因为论点中没有任何内容总和7
我的问题是，给定一组参数数字，SUBSET-SUM是否存在可能解决方案数量的多项式上限。在第一个示例中，有(2,4)和(1,5)。
我们知道，既然SUBSET-SUM在多项式时间内确定 NP 完全可能是不可能的。但是我的问题与决策时间无关，我严格询问解决方案列表的大小。
显然，参数数的幂集的大小可以是解决方案列表大小的上限，但是这具有指数增长。我的直觉是应该有一个多项式界限，但我无法证明这一点。
nb我知道这听起来像是一个家庭作业问题，但请相信我不是。我正在尝试自学 CS 理论的某些方面，这就是我的想法。
不; 取数：
(1, 2, 1+2, 4, 8, 4+8, 16, 32, 16+32, ..., 2 2n , 2 2n+1 , 2 2n +2 2n+1 )
并询问形成总和 1 + 2 + 4 + ... + 2 2n + 2 2n+1。（例如：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 2n和 2 2n+1或 2 2n +2 2n+1形成 2 2n + 2 2n +1 。
选择是独立的，因此至少有 3 n =3 m/3，其中 m 是您的集合的大小。我敢打赌这可以大大加强，但这证明没有多项式界限。
斯珀纳定理提供了一个很好的（尽管是非多项式的）上限，至少在集合中的数字严格大于零的情况下（您的问题似乎就是这种情况）。
具有给定总和的所有子集的族形成一个Sperner 族，它是子集的集合，其中该族中的任何子集本身都不是该族中任何其他子集的子集。这是使用元素严格大于零的假设的地方。Sperner 定理指出，此类 Sperner 族的最大大小由二项式系数 给出n Choose floor(n/2)。
如果你放弃数字不同的假设，n很容易看出这个上限无法改进（只需取所有数字 = 1 并让目标总和为floor(n/2)）。我不知道在数字不同的假设下是否可以改进。