Meditations on Quantified Constraint Satisfaction

VCLA will be hosting a talk by Hubie Chen on April 22nd, 2013.

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.

In this talk, we discuss two lines of work aimed at understanding the complexity of the QCSP.

In the first part, we will study the QCSP on fixed structures: 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^2, ... 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 between computational complexity, universal algebra, and logic.

In the second part, we will discuss the QCSP where the sentences are restricted. Here, one obtains a family of problems by defining, for any set Phi of QCSP sentences, the problem Phi-QCSP to be the restricted version of the QCSP where the sentence must come from Phi (but the structure may be set freely). We will discuss the quest to understand the complexity of which sentence sets Phi yield a problem Phi-QCSP that is tractable, a quest that will involve visiting notions such as treewidth, finite-variable logics, and parameterized complexity.

The first part of this talk will partially be based on the overview article available at http://arxiv.org/abs/1201.6306.