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

programming

Statement

Lemma

k-SAT is NP-complete for $k \geq 3$

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 $k \geq 3$, as a CNF with at most $3$ terms has at most $k$ terms for $k \geq 3$.

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