證明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）現在微不足道 - 我寧願不去做其餘的事情。