# 2012 seminar talk: Meditations on Quantified Constraint Satisfaction

Talk held by Hubie Chen (Universitat Pompeu Fabra, Barcelona, Spain) at the KGRC seminar on 2012-05-03.

### Abstract

The quantified constraint satisfaction problem (QCSP) is the computational problem of deciding, given a structure and a first-order prenex sentence whose quantifier-free part is the conjunction of atoms, whether or not the sentence holds on the structure. One obtains a family of problems by defining, for each structure*B*, the problem

*QCSP(B)*to be the QCSP where the structure is fixed to be

*B*. We will discuss the research program of trying to classify the complexity of

*QCSP(B)*for each finite structure

*B*. It is possible to associate an algebra to each finite structure in such a way that studying the algebra of a structure gives insight into the QCSP complexity of the structure. We will overview the use of universal-algebraic notions and techniques in this research program. In particular, there is a close connection between QCSP complexity and the growth rate of the number of elements needed to generate the powers

*A*,

^{1}*A*, ... of an algebra

^{2}*A*: showing an at-most polynomial growth rate can (essentially) be translated to a complexity upper bound for a structure with algebra

*A*. This research area gives (we believe) a fascinating interplay among computational complexity, universal algebra, and logic.

This talk will partially be based on the overview article available at http://arxiv.org/abs/1201.6306.