子集和，解数的上界

Question

您可能知道，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理论，这是我的想法带我。

Answer 1

Sperner定理提供了一个很好的上限(尽管不是多项式)，至少在集合中的数字严格大于零的情况下是这样(就像您的问题中的情况一样)。

具有给定和的所有子集的族构成了Sperner族，它是一个子集的集合，其中该家族中没有子集本身是该家族中任何其他子集的子集。这是使用元素严格大于零的假设。Sperner定理指出，这类Sperner族的最大大小是由二项式系数n Choose floor(n/2)给出的。

如果您放弃了n数是不同的假设，很容易看到这个上限不能得到改进(只需取所有数字=1，并让目标和为floor(n/2))。我不知道在假设数字是不同的情况下，它是否能得到改进。