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¹, A², ... of an algebra 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.