ИСТИНА

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. For over twenty years one of the main question was to classify constraint languages giving a tractable (solvable in polynomial time) CSP (like system of linear equations, 2-CNF, and so on). In 2017 the conjecture describing all tractable cases was independently proved by A. Bulatov and D. Zhuk. In this talk I will argue that despite the fact that plenty of deep algebraic results and even theories appeared while studying the complexity of CSP, now we can say that Constraint Satisfaction Problem is actually easy.