PART A. Computationally Hard Instances

I’ll use the propositional satisfiability problem (SAT)to illustrate ideas and concepts throughout this talk.
SAT: prototypical hard combinatorial search and reasoning problem.

Several of these concepts have also been studied in the context of Constraint Satisfaction Problems. In particular, see the work by Cheeseman and colleagues (1991).