Algebra Seminar talk
10:15 (Dissertantenraum)
Dmtrij Zhuk
The complexity of the Constraint Satisfaction Problem and its variations
Abstract:
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.