k-SAT is in NP

Statement

Lemma

k-SAT is in NP

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 we have to check each clause, with each clause we check of the variables which takes at most time - polynomial in the input size.

Therefore k-SAT is in NP.