Algebra Seminar talk
The complexity of the Constraint Satisfaction Problem and its variations
Many combinatorial problems, such as graph coloring and solving linear equations, can be expressed as the constraint satisfaction problem for some constraint language. In 2017 the complexity of the constraint satisfaction problem was described for any constraint language on a finite set, but there are many other variants of this problem whose complexity is still not known. For instance, we could allow to use both universal and existential quantifiers, or require the solution to be surjective or balanced. Another variant is to require the input to satisfy an additional condition. As an example we could consider the problem of coloring a graph in 100 colors if we know that the graph is colorable in 3 colors. In the talk we discuss the complexity of these and other variants of the constraint satisfaction problem.