12 February 2019
Czech Academy of Sciences
Reasoning and Logic Department
Amanda Vidal

The study of the complexity classification of the (non-uniform) Constraint Satisfaction Problem and of some of its valued variants has lived an enormous development from the 90s, when the dichotomy conjecture was proposed by Feder and Vardi. The question was (roughly) whether, fixed a template (i.e., a set of possible restrictive relations over a finite universe), determining if an arbitrary  CSP over it had a solution or not was either in P or NP-complete. Of being true, this would turn non-uniform CSP into one of the biggest classes of problems with this separating property, contributing to the understanding of the PvsNP question. Studying this problem, and developing complexity classifications based on algebraic properties of the structures of certain maps associated to templates, has become an important branch in the intersection of Theoretical Computer Science with Universal Algebra.

The dichotomy was proven in 2018 independently by two researchers, providing a full complexity classification of the CSP question, and extending to the so-called Valued CSP. This latter problem concerns a relaxation of the question, but choosing a quite particular setting (assign weights of constraints in Q with a top element, and search for a minimal sum).

In this seminar we will do a light overview of the algebraic approach to CSP and VCSP, and then explore other problems and possible approaches arising from a setting of weighted constraints over richer structures, and focused in minimazing/maximazing other possible formulas over the weights of the constraints.

Institution department: 
Institute of Computer Science