如您所知，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，...，22n，22n + 1、22n + 22n + 1)
并询问关于求和1 + 2 + 4 + ... + 22n + 22n + 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。
....
您可以使用22n和22n + 1或22n + 22n + 1形成22n + 22n + 1。
选择是独立的，因此至少有3n = 3m / 3，其中m是集合的大小。我敢打赌，这可以大大加强，但这证明没有多项式界。