|4:00 pm Monday, October 10, 2011|
Computer Science Colloquium: The Mathematics of Constraint Satisfaction
Matt Valeriote (McMaster University) in Keck 100
A reception will be held beginning at 3:30 PM in Duncan Hall, Room 3076. Host Department: Rice University-Mathematics
Many important problems from combinatorics, logic, and computer science can be expressed as instances of the constraint-satisfaction problem (CSP). For example, instances of graph k-colorability for some k and instances of boolean satisfiability can be regarded as CSPs. While the class of constraint-satisfaction problems is known to be NP-complete, there are many natural subclasses of it that are tractable. It is conjectured by Feder and Vardi that in fact any such naturally defined subclass is either tractable or is NP-complete. In my talk I will introduce the class of CSPs and then discuss an approach via algebra to settle the Feder-Vardi Dichotomy Conjecture.
Submitted by firstname.lastname@example.org