Problem (New-SAT) 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...

Problem (New-SAT)

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 isNP-complete. Reduce an NP-hard problem from Section 12.13 (Other Useful NP-hard Problems).