证明NP完全

Question

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

下面是问题： 子集和问题显示为NP完全。输入是一系列正数w1，...，wn，W，其中W是目标权重。问题是要确定是否有一组权重F⊆{1，...，n}，使得某些权重之和等于目标权重（即w1 + ... + wi = W）
设定受限子集总和问题如子集总和一样，但是额外要求目标权重小于所有权重总和的一半。 （如果失败，则必须立即拒绝输入。）显示受限子集和是NP完全的。
谢谢。

Answer 1

你必须显示（a）你的问题在NP和（b）你的问题是NP难。对于（a），证明NP中某个问题的解决方案可以使解决问题变得简单（如果仔细考虑，则显示这一点很简单）。对于（b），你需要证明你的问题的一个解决方案可以解决NP中的任何问题（换句话说，找到另一个NP完全问题的解决方案可以用你的问题的解决方案来解释）。

这实际上已经有一半的证据 - （a）现在微不足道 - 我宁愿不去做其余的事情。