The Proof of CSP Dichotomy Conjecture.

Many natural combinatorial problems can be expressed as constraintsatisfaction problems. This class of problems is known to be NP-complete ingeneral, but certain restrictions on the form of the constraints can ensuretractability. The standard way to parameterize interesting subclasses of theconstraint satisfaction problem is via finite constraint languages. The mainproblem is to classify those subclasses that are solvable in polynomial timeand those that are NP-complete. It was conjectured that if a core of aconstraint language has a weak near unanimity polymorphism then thecorresponding constraint satisfaction problem is tractable, otherwise it isNP-complete.

In the paper we present an algorithm that solves Constraint SatisfactionProblem in polynomial time for constraint languages having a weak nearunanimity polymorphism, which proves the remaining part of the conjecture.