"4-SAT"

Consider the 4-SAT problem. This takes the same form as 3-SAT, but each

of the k clauses now includes 4 terms instead of 3. Prove that 4-SAT is NP-complete.

a) Show that 4-SAT is NP, by giving a polynomial-time algorithm for verifying a

certicate which is a (claimed) satisfying assignment for the n Boolean variables (x_1, x_2 , .... x_n).

b) Describe the steps of a reduction from an arbitrary 3-SAT instance, to a specially-

constructed 4-SAT instance, to the retrieval of a satisfying assignment to the original 3-SAT

instance from the black box result.

c) Prove that the 3-SAT instance is satisable => the constructed 4-SAT instance is

satisable.

d) Prove that the constructed 4-SAT instance is satisable => the original 3-SAT

instance is satisable.