# Statement

# Proof

k-SAT is in the correct form for a search problem . It either outputs an assignment that satisfies the formula or it says no such assignment exists.

To check an assignment $S$ we have to check each clause, with each clause we check $k$ of the variables which takes at most $O(nm)$ time - polynomial in the input size.

Therefore k-SAT is in NP .