SAT

To prove a problem is NP-hard, it helps to have other NP-hardness problems around to reduce to it.

Cook proved the first NP-hard problem.

3CNF-SAT (sometimes just SAT) is a popular version of the problem:

• Given a Boolean formula in conjunctive normal form with at most 3 variables per clause, is there an assignments to its variables that makes the formula true?

Example...

SAT is in NP: assignment is the certificate.

SAT is NP-hard essentially because we can ``build'' a special guessing computer out of logic gates. We can write any problem in NP as a program for this computer.

This computer has some non-deterministic components that express an accepting certificate. The formula will be satisfiable only if the computer will print ``yes'' for some certificate.