np-complete - 证明 NP 完全

Question

大家好，我有一个问题。我想知道是否有人知道如何证明它。

这是问题：子集和问题被证明是NP完全的。输入是一系列正数 w1, ... ,wn, W，其中 W 是目标权重。问题是判断是否存在一组权重 F ⊆ {1, ... ,n} 使得一些权重之和等于目标权重（即 w1 + ... + wi = W
） Restricted Subset Sum 问题可以像 Subset Sum 一样定义，但额外要求目标权重小于所有权重总和的一半。（如果失败，则必须立即拒绝输入。）证明 Restricted Subset Sum 是 NP-complete。
谢谢你。

Answer 1

你必须证明（a）你的问题是 NP 和（b）你的问题是 NP 难的。对于（a），证明解决 NP 中的某个问题会使解决问题变得容易（如果您考虑一下，证明这是微不足道的）。对于（b），您需要证明您的问题的解决方案将使解决任何 NP 问题变得容易（换句话说，找到另一个 NP 完全问题，其解决方案可以根据您的问题的解决方案重新表述）。

这实际上已经是证明的一半——（a）现在是微不足道的——我不想做剩下的。