Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2014/iii/paper-37/6/a/solution

Let be the number of true values among . Count the ten clause occurrences for the two choices of . With , the three positive singletons contribute , the three negated-pair clauses contribute , and the last three clauses all hold. With , the four singleton clauses contribute , the negated pairs again contribute , and the last three contribute . Therefore
The original three-literal clause is satisfied exactly when , and then a value of satisfies exactly seven gadget clauses. If , no choice reaches seven. Thus the required equivalence holds, and seven is also an upper bound for every assignment to the gadget. This is the seven-clause gadget for MAX-2SAT.

New to topics? Read the docs here!