Page 1 of 1
Question 6[10]. Input: You are given a 3-SAT formula. A true value is considered as (+1) and a false value is considered
Posted: Sat Nov 27, 2021 10:27 am
by answerhappygod
- Question 6 10 Input You Are Given A 3 Sat Formula A True Value Is Considered As 1 And A False Value Is Considered 1 (112.43 KiB) Viewed 104 times
Question 6[10]. Input: You are given a 3-SAT formula. A true value is considered as (+1) and a false value is considered (-1).
Question: Does there exist a truth-value assignment for each variable such that the sum of the three variables of each clause is between -1 and 1? Show that the problem is NP-complete. Reduce an NP-hard problem from Section 12.13 (Other Useful NP-hard Problems).