Boolean Satisfiability Problem

In Boolean Satisfiability Problem (SAT), we try to solve a formula composed of boolean expressions. If we find a way so the formula is true, it is satisfiable.

For example, the formula (A OR B) AND (A AND NOT B) is satisfiable if A is true and B is false.

Cook-Levin theorem

The Cook-Levein theorem says that the SAT problem is NP-Complete.

It also says that any NP problem can be reduced to an instance of a SAT problem. It means that if we can solve it in polynomial time, we can solve any NP problem in the same way, and the P vs. NP problem would be solved.