The Satisfiability problem is in NP

Statement

Lemma

The Satisfiability problem is in NP.

Proof

First note that it is in the form of a search problem as it either provides you with a satisfying assignment to the 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 -variables. To check one clause is satisfied takes time. There are clauses, so this in total takes time.

This is polynomial so the Satisfiability problem is in NP.