Local consistencies in SAT

Toby Walsh

(Cork, Ireland)

Propositional satisfiability (SAT) and constraint satisfaction problems (CSPs) are closely related NP-complete problems. In this talk, I explore some of these connections. I show how a wide variety of inference methods (so called "local consistencies") in CSPs can be simulated by unit propagation, the basic inference method in SAT. Technology developed for SAT solving can therefore be readily used to solve CSPs. Joint work with Emmanuel Hebrard and Brahim Hnich (4C, Cork, Ireland) and Christian Bessiere (LIRMM, Montpelier, France).
Tuesday 24th June 2003, 14:00
Robert Recorde Room
Department of Computer Science