如何证明观影决策问题为NP难问题 能否选用子集和问题归约

首先先明确你当前的描述存在一个待补全的核心约束：你没有提到选择推荐者的优化/判定目标，否则随便选t/2个推荐者就满足要求，问题不存在复杂度属性。默认你补充的约束是：每个推荐者对应一个正收益值（比如推荐的电影匹配度），你要在总时间t内选恰好t/2个推荐者，最大化总收益，对应的判定版本为是否存在大小为t/2的推荐者子集，总沟通耗时不超过t（剩余时间用于观影）且总收益不低于给定阈值V。

能否用子集和完成归约 #

答案是完全可以，子集和是非常适配的归约源问题，你也可以选用带基数约束的0-1背包、固定大小子集和这两类已知NP难问题完成归约，后者步骤会更简洁。

子集和归约的具体操作步骤 #

我们先明确子集和的标准判定版本：给定正整数集合A = {a_1, a_2, ..., a_n}，目标和K，问是否存在子集A' ⊆ A，使得A'的元素和恰好为K。
归约构造流程如下：

1. 取任意子集和实例(A, K)，我们构造你的问题实例：
   • 设定总可用时间t = 2K，要求选择的推荐者数量固定为t/2 = K
   • 新增K个额外的虚拟推荐者，每个虚拟推荐者的收益为0，沟通耗时固定为1小时
   • 每个子集和的元素a_i对应一个真实推荐者，收益为a_i，沟通耗时固定为1小时
   • 你的问题的判定条件设为：是否存在t/2个推荐者，总收益≥K
2. 双向等价性证明：
   • 若子集和实例有解：设子集A'的和为K，子集大小为m，我们从虚拟推荐者中选K - m个补入，刚好凑够K个推荐者，总收益为K，满足你的问题的判定条件
   • 若你的问题实例有解：选了K个推荐者总收益≥K，由于所有真实推荐者的收益都是正整数、虚拟推荐者收益为0，总收益恰好等于K，其中的真实推荐者对应的元素就是子集和实例的解
3. 构造过程是多项式时间的，因此你的问题属于NP难问题。

内容的提问来源于stack exchange，提问作者sow