Spring 2018 Seminars
|Time: Monday, January 23 2018, 4:10 PM
Place: SC 1312
Speaker: Andrew Moorhead
Title: The Algebraic Approach to the Constraint Satisfaction Problem (Part I)
Abstract: The Constraint Satisfation Problem is a general combinatorial problem that asks whether there exists an assignment of values belonging to some finite domain to a finite set of variables subject to certain constraints. The Constraint Satisfaction Problem Dichotomy Conjecture is the statement that this problem is either solvable with a polynomial time algorithm or is complete for the class NP. A fruitful line of investigation into this problem has been to associate to a given template of constraints a universal algebra that consists of all higher order symmetries, or polymorphisms, of the relational structure determined by the template. This series of talks will introduce the Constraint Satisfaction Problem with the ultimate goal of understanding the recently proposed proofs of the Dichotomy Conjecture.