Satisfiability
SAT: Given a formula in propositional calculus, is there an assignment to its variables making it true?
We consider clausal form, e.g.:
(a b c) ( b d (b c e) . . .
Problem is NP-Complete. (Cook 1971)
Shows surprising “power” of SAT for encoding computational problems.