This installment of the notes describes discrete constraint satisfaction problems and various algorithms which have been developed in AI for finding solutions. The notes emphasize the NP-complete nature of these problems and briefly discusses the general nature of the complexity class NP. The AI algorithms are based on various strengths of "consistency" that have been discussed in the AI literature. Implementations of consistency notions using inference rules is also discussed.
David McAllester, February, 1995