Description
Problem 1 (25pts)
Consider the partial satisfiability problem, denoted as 3-Sat(α). We are given a collection of k clauses, each of which contains exactly three literals, and we are asked to determine whether there is an assignment of true/false values to the literals such that at least αk clauses will be true. Note that 3-Sat(1) is exactly the 3-SAT problem from lecture.
Prove that 3-Sat(15/16) is NP-complete.
Hint: If x, y, and z are literals, there are eight possible clauses containing them: (x ∨ y ∨z), (!x ∨y ∨z), (x∨!y ∨z), (x ∨y∨!z), (!x∨!y ∨z), (!x ∨y∨!z), (x∨!y∨!z), (!x∨!y∨!z)
5
