PPT Slide
To show a set of clauses S unsatisfiable, we need to demonstrate (“prove”) that none of the 2 truth assignments satisfies S.
This “truth-table” method is very time consuming.
Compare this with having to check a single satisfying assignment to verify the satisfiability of a formula.
Can we do better? --- Surprisingly difficult!