Let L_sat be Boolean Satisfiability, and let L_3-sat be the subset of that language consisting of satisfiable formulae of the form C_1 C_2 ... C_n, where each ``clause'' C_i is of the form (a_1+a_2+a_3), where each a_i is the form either x_j or x_j for some j. Prove that L_3-sat is NP-complete.
Hint. We say that C is a 3-clause if C = (a_1+a_2+a_3), where each a_i is a variable or the negation of a variable. Similarly, we can define 4-clause, 5-clause, and so forth.
Every 1-clause is also a 2-clause, and every 2-clause is also a 3-clause, and so forth. This is because (a_1+a_2) is equivalent to (a_1+a_1+a_2). Going the other way is much harder.
Let me show you just one example by which a 4-clause can be reduced to a conjunction of 3-clauses. Suppose that variables x_i have been defined for all i up to N-1. Then x_N is a variable name that is not previously used.
Write ~x to mean not x.
We need to create a conjunction of 3-clauses which is satisfiable if and only if the 4-clause (x_1+x_2+x_3+x_4) is satisfiable. The trick is to find a formula involving only 3-clauses which makes x_N equivalent to x_3+x_4. Conjoining that formula with (x_1+x_2+x_N) will give us what we need.
In general, we use the fact (out of your logic course) that ~p+q means 'p implies q'.
The clause (x_3+x_4+~x_N) means 'x_N implies x_3+x_4.'
The clause (~x_3+x_N) means 'x_3 implies x_N.'
The clause (~x_4+x_N) means 'x_4 implies x_N.'
Thus, (x_1+x_2+x_3+x_4) is satisfiable if and only if
(x_1+x_2+x_N)(x_3+x_4+~x_N)(~x_3+x_N)(~x_4+x_N)
You need to show that every k-clause, for k > 3, can be reduced to a conjunction of 3-clauses.
Why not 2-clauses instead? Becuase it is not always possible to reduce a 3-clase to the conjunction of 2-clauses.