Boolean Satisfiability Problem (SAT)

The Boolean Satisfiability Problem (SAT) takes an input of:

• a propositional formula $F$ in CNF

It provides an output of $\top$ if and only if $F$ is satisfiable.