The constraint satisfaction problem (CSP) involves deciding, given a set of variables and a set of constraints on the variables, whether or not there is an assignment to the variables satisfying all of the constraints. One formulation of the CSP is as the problem of deciding, given a pair (G,H) of relational structures, whether or not there is a homomorphism from the first structure to the second structure. The CSP is in general NP-hard; a common way to restrict this problem is to fix the second structure H, so that each structure H gives rise to a problem CSP(H). The problem family CSP(H) has been studied using an algebraic approach, which links the algorithmic and complexity properties of each problem CSP(H) to a set of operations, the so-called polymorphisms of H. Certain types of polymorphisms are known to imply the polynomial-time tractability of CSP(H), and others are conjectured to do so.
In a recent joint article with B. Larose, we systematically study---for various classes of polymorphisms---the computational complexity of deciding whether or not a given structure H admits a polymorphism from the class. Among other results, we prove the NP-completeness of deciding a condition conjectured to characterize the tractable problems CSP(H), as well as the NP-completeness of deciding if CSP(H) has bounded width. In this talk, I will describe some of the main results from this article.
This talk is based on the article available at https://arxiv.org/abs/1604.00932.
Asking the metaquestions in constraint tractability Sponsored by the Meyer Fund
Nov. 01, 2016 2pm (MATH 220)
Hubie Chen (San Sebastian)
X
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^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.
This talk will partially be based on the overview article available at http://arxiv.org/abs/1201.6306.
Meditations on Quantified Constraint Satisfaction Sponsored by the Meyer Fund
Nov. 01, 2016 3pm (MATH 350)
Topology
David Gepner (Purdue U)
X
In this talk we will give a gentle introduction to chromatic homotopy theory with emphasis on the close connection between algebraic topology and algebraic geometry which arises from the theory of formal groups. We will then consider how this relationship can be made even closer by enlarging our scope to include spaces with group actions, and what this amounts to in the interesting case of elliptic cohomology.