Seminar:
           Beyond NP: Reasoning on Quantified Constraints
By:
                           Toni Mancini
               http://www.dis.uniroma1.it/~tmancini/
                   Dipartimento di Informatica
                Sapienza Università di Roma, Italy
On:
                   Tuesday 20th of January 2009
                       at 11:15 in room 1211
         of http://www.polacksbacken.uu.se/index_itc.shtml

Abstract: 

Quantified constraints and Quantified Boolean Formulae are typically
much more difficult to reason with than classical constraints, because
quantifier alternation makes the usual notion of "solution"
inappropriate.  As a consequence, basic properties of Constraint
Satisfaction Problems (CSP), such as consistency or substitutability,
are not completely understood in the quantified case.  These
properties are important because they are the basis of most of the
reasoning methods used to solve classical (existentially quantified)
constraints, and one would like to benefit from similar techniques in
the resolution of quantified constraints.

In this talk, we show that most of the properties used by solvers for
CSPs can actually be elegantly generalized to quantified CSPs,
provided that a re-thinking of a number of basic concepts, like that
of "solution", is made.  Semantical relations holding between the
various properties (for both CSPs and quantified cases), as well as
complexity results regarding their decision problems will also be
discussed.