The 39th GRACE Seminar on Advanced Software Science and Engineering
http://grace-center.jp/
Time: 11:00-12:00, August. 11th, 2010
Place:Meeting Room (2009/2010), 20F, National Institute of Informatics
(map)
Inquiry: Hiroyuki Kato (kato_AT_nii.ac.jp)
Fee: Free
Please register via the following page:
http://grace-center.jp/regist/seminar
======================================================
SPEAKER
Prof. Toby Walsh（NICTA and University of the New South Wales）
=== Title ===
What can we do in SAT?
=== Abstract ===
SAT solvers have matured into a powerful turn key technology for solving a wide range of combinatorial problems. In this talk, I look at what we can and cannot do effectively in SAT. The talk explores in addition the connections between SAT and Constraint Satisfaction. The focus of the talk is on global constraints like AllDifferent. These are one of the key distinguishing features of constraint programming. I describe recent work on simulating the actions of global constraints with simple decompositions that can be implemented using SAT clauses or ILP models. Based on powerful lower bounds from circuit complexity,
I argue that there are, however, some things that cannot be effectively simulated in SAT. The conclusion is that not everything can be done in SAT and we do in fact need some of the powerful algorithmic techniques provided by Constraint Satisfaction.
