ИСТИНА

In 2007 it was conjectured that the Constraint Satisfaction Problem (CSP) over a constraint language Γ is tractable if and only if Γ is preserved by a weak nearunanimity (WNU) operation. After many efforts and partial results, this conjecture was independently proved by Andrei Bulatov and the author in 2017. In this talk we consider one of two main ingredients of author’s proof, that is, strong subalgebras that allow us to reduce domains of the variables iteratively. The idea of the approach is that every idempotent algebra has a sualgebra of one of the following five types: binary absorbing, central, PC, projective or linear. These subalgebras have additional strong properties, which allow us to reduce the domain iteratively maintaining some property. Since we consider only finite algebras, finally we get a one-element subalgebra, for which the required fact is obvious. To explain how this idea works we show the algebraic properties of strong subalgebras and present a simple proof of several important (and known) facts about the complexity of the CSP. First, we prove that if a constraint language is not preserved by a WNU operation then the corresponding CSP is NP-hard. Second, we characterize all constraint languages whose CSPs can be solved by local consistency checking. Additionally, we characterize all idempotent algebras not having a WNU term of a concrete arity n, not having a WNU term, having WNU terms of all arities greater than 2.