This repository collects some resources for learning the basics of Constraint Satisfaction Problems.
First, it is important to know a little bit of complexity theory. You can pick up the essentails (which is all we'll need) from Wikipedia. I've collected the most relevant entries here:
https://en.wikipedia.org/wiki/User:Williamdemeo/Books/Complexity_Theory
An alternative with lots more details is here:
https://en.wikipedia.org/wiki/User:Williamdemeo/Books/Complexity,_Computability,_and_Types
(If you want to help "edit" this "book" by adding other pages that you have read and found particularly useful, let me know and I'll give you book editing privileges.)
Here are some references for learning about the algebraic approach to CSP:
-
Cliff Bergman's nice summary of some important CSP concepts: seminar handout
-
Miklos Maroti's overview of CSP: slides
-
Benoit Larose's broad overview of CSP and Algebra: slides
-
Ross Willard's slides from SSAOS 2014: lecture 1, lecture 2, lecture 3 (very nice presentation; lots of details about the basics; some interesting new ideas)
-
Libor Barto's overview: paper
-
David Failing's phd thesis has lots more details: thesis
Basic facts about the algebraic CSP-dichotomy conjecture: open notebook entry
A connection between 3-SAT and partition lattices: open notebook entry