# Statement

# Proof

First note that it is in the form of a search problem as it either provides you with a satisfying assignment to the $n$ variables or says one doesn’t exist.

All that is left to show is that we can verify an answer in Polynomial time .

Given an assignment of values to the $n$-variables, checking whether one clause is satisfied takes $O(n)$ time. There are $m$ clauses, so in total this takes $O(nm)$ time.

This is polynomial so the Satisfiability problem is in NP .