CS计算机代考程序代写 SUBSET-SUM

SUBSET-SUM
and Related Problems

SUBSET-SUM
• Recall, the subset-sum problem is the following language: 𝑙 {𝑆,𝑡:𝑆= 𝑥,…,𝑥 ,andforsome 𝑦,…,𝑦 ⊆ 𝑥,…,𝑥 ,෍𝑦 =𝑡}
1𝑛 1𝑙1𝑛𝑖 𝑖=1
• Inputs: an integer value (target) t, and a set of integers 𝑎1, … , 𝑎𝑛 • Output: YES if there is a subset that adds up to t, NO otherwise

SUBSET-SUM is in NP • Proof: Sipser Theorem 7.25

SUBSET-SUM is in NPc • Proof: Sipser Theorem 7.56
• We show that 3𝑆𝐴𝑇 ≤𝑝SUBSET-SUM • How?
• Given a 3CNF formula ∅, we want (within polytime in the length of ∅) to create(build) an instance of SUBSET-SUM (dependent on ∅):
𝑆 ,𝑡 suchthat∅issatisfiableiff𝑆 hasasubsetthataddsupto𝑡 . ∅∅∅∅

From∅to 𝑆 ,𝑡 ∅∅
• Suppose it has variables 𝑥 ,…,𝑥 and clauses 𝑐 ,…,𝑐 1𝑙 1𝑘
• 𝑡∅ = 11…133…3 (decimal number) 𝑙𝑘
• Example: If 𝑙 = 1 and 𝑘 = 1, then 𝑡∅ is thirteen
If∅= 𝑥1∨¬𝑥2∨¬𝑥3 ∧ 𝑥3∨¬𝑥4∨𝑥5 ,then 𝑡∅ = 1111133

𝑆=?? ∅
(1) If 𝑥𝑖 is a variable in the formula ∅ and the literal 𝑥𝑖 appears in the clauses𝑐 ,…,𝑐 ,thenincludein𝑆 thenumber𝑌 =:
𝑗1𝑗𝑟 ∅𝑖
100…00…1…010…0 𝑙−𝑖 𝑘
Where in red, the 1’s are in the positions 𝑗 , … , 𝑗 1𝑟
(2) Do the exact same for the literal ¬𝑥𝑖. Call the resulting number 𝑍𝑖 (3)Foreachclause𝑐,include𝐷 =100…0and𝐻 =200…0
𝑗𝑖𝑖
𝑘−𝑗 𝑘−𝑗

This construction works
(1) If ∅ is satisfiable, we can find a subset T of 𝑆 such that the sum of
the elements in T equals 𝑡∅
(2) Conversely, if we can find a subset T of 𝑆 such that the sum of the
∅ elements in T equals 𝑡∅ , then ∅ is satisfiable
∅

(1)
• Supposethat∅issatisfiable(bysomeassignment);herewebuildT
• If 𝑥 is assigned TRUE, include 𝑌 in T
𝑖𝑖
• If 𝑥𝑖 is assigned FALSE, include 𝑍𝑖 in T
• Withtheelementsincludedsofar,thesumoftheelementsinTshouldbesomethinglike 11…123..1..3
𝑙𝑘
(the last k digits are made from 1,2,3)
• Ifneeded,includeinTfrom𝐷 and𝐻 whatbringsupthesumto11…133…3 𝑖𝑖
𝑙𝑘

(2)
• Suppose we can find a subset T of 𝑆 such that the sum of the
elements in T equals 𝑡∅
• We build an assignment which satisfies ∅
• If T contains 𝑌 , then assign 𝑥 to TRUE 𝑖𝑖
• If T contains 𝑍𝑖 , then assign 𝑥𝑖 to FALSE
∅

(2) Clarified
• Note that all we know about T here is that it is a collection of 𝑌 ’s,
𝑍’s,𝐷 ’s,and𝐻 ’s 𝑗𝑚𝑛
• They all add up to 11 … 1 33 … 3 𝑙𝑘
𝑖
• The 1’s at the beginning imply that for each variable 𝑥𝑖 , exactly one of 𝑌 or 𝑍 is in T
𝑖𝑖
•These𝑌 ‘s(or𝑍’s)contributeatleasta1toeach3 𝑖𝑖

Related Posts