# Statement

# 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 be used to reduce the SAT problem to k-SAT for all $k \geq 3$, as a CNF with at most $3$ literals per clause has at most $k$ literals per clause for $k \geq 3$.

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