第39回先端ソフトウェア科学・工学に関するGRACEセミナー

主催:NII 先端ソフトウェア工学国際研究センター(GRACEセンター)
http://grace-center.jp/
日時:2010年8月11日(水)11:00-12:00
場所:国立情報学研究所(NII) 20階ミーティングルーム(2009/2010)  (地図
参加費:無料
お問い合わせ:加藤 弘之 (kato_AT_nii.ac.jp)_AT_を@に書き換えてください。

参加をご希望の方は、セミナー前日までに下記よりご登録をお願いします。
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.

カテゴリー: 研究, セミナー パーマリンク

コメントは停止中です。