Minicourse on CSP - Talk 2 - Meditations on Quantified Constraint Satisfaction

The quantified constraint satisfaction problem (QCSP) is the natural generalization of the CSP where universal quantification is permitted. Precisely, the QCSP is the 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. As with the CSP, one obtains a family of problems is by defining, for each structure B, the problem QCSP(B) to be the QCSP where the structure is fixed to be B. In this talk, we offer a viewpoint on the current status of the research program of understanding the complexity of the problems QCSP(B) on finite structures. In particular, we will present and discuss a group of conjectures on this problem family; throughout, we will place the conjectures in relation to existing results and will emphasize open issues and potential research directions. One of the leading protagonists of these conjectures is a property of algebras called the polynomially generated powers (PGP) property: essentially, an algebra A has this property when its powers A, A^2, A^3,... have generating sets of polynomial size. (This talk will be roughly based on an article of the same title which I will make available.)