We define the following problem, which we call 3-SAT(a). We are given a collection of m clauses, each of which contains exactly three literals (variables), and asked to determine whether there is an assignment of true/false values to the literals such that at least a*m clauses will be true. Note that 3-SAT(1) is exactly the 3-SAT problem.
(a) Give an O(m*n)-time algorithm that outputs a satisfying assignment for 3-SAT(1/2).
(b) Prove that 3-SAT(15/16) is NP-complete. Hint: Consider the collection of all possible 3-SAT clauses on three literals. Any truth assignment to the literals will make exactly seven of these clauses true (and one false).