k-SAT is NP-complete for k greater than or equal to 3

Statement

Lemma

k-SAT is NP-complete for

Proof

Note that k-SAT is in NP.

Separately we have shown 3-SAT is NP-complete. In this proof we showed a reduction of the SAT problem to 3-SAT. The clause reduction in this takes a SAT problem and reduces it to a problem in 3-SAT. The same reduction can we used to reduce the SAT problem to k-SAT for all , as a CNF with at most terms has at most terms for .

Therefore k-SAT is NP-hard and in NP so is NP-complete.