Constraint Satisfaction Problem: known results and open problems

The Constraint Satisfaction Problem (CSP) is the problem of deciding whether there is an assignment to a set of variables subject to some specified constraints. In general this problem is NP-complete and one of the ways to make it solvable in polynomial time (tractable) is by restricting the set of allowed constraints. For over twenty years one of the main questions was to classify constraint languages giving a tractable CSP (like system of linear equations, 2-CNF, and so on). In 2017 the conjecture describing all tractable cases on a finite set was resolved but many other questions still remain open. In the talk we will discuss the following and some other generalizations of the CSP.

• Can we solve a system of linear equiations in $\mathbb Z_{2}$ in polynomial time if we add to it one equation modulo $k$?
• If the only predicate we can use is $x+y\neq 2$ on $\mathbb Z_{3}$, then every instance of the CSP has a trivial solution $(0,0,\dots,0)$. Can we check in polynomial time whether the instance has a surjective solution (every element from the domain appears in the solution)? What is the complexity of this problem for other constraint languages?
• Constraint satisfaction problem can be formulated as a sentence where all variables are existentially quantified. If we allow universal quantification then the problem is PSpace-complete in general but for some constraint languages it can be tractable, NP-complete, coNP-complete, and so on. What is the complexity of this problem for each constraint language?
• Assume that we have a strong and a weak versions of every predicate in a constraint language, and we have a promise that either strong version of the instance has a solution or even weak version has no solutions. Sometimes such a promise makes an NP-hard problem tractable. But it is still not clear what is the complexity of the following problem. Given a graph which is either 3-colorable, or not even 1000-colorable. We need to distinguish between these two cases.
  
• What if we additionally require every variable of an instance to appear exactly twice? This formulation covers the well-known perfect matching problem. The complexity of this problem for an arbitrary constraint language is still open.