Hubie Chen, University of the Basque Country and Ikerbasque
“Generating Powers of Algebras: How, When, and Why”
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 A1,A2, ... 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.
This talk will partially be based on the overview article available at Meditations on Quantified Constraint Satisfaction.
Special presentation.