Constraint Satisfaction Problem: what makes the problem easy

Many combinatorial problems, such as graph coloring or solving linear equations, can be expressed as the constraint satisfaction problem for some constraint language. In the talk we first discuss a proof of a famous conjecture stating that for any constraint language the problem is either solvable in polynomial time, or NP-complete. Then we consider other variants of this problem whose complexity is still not known. For instance, we could allow both universal and existential quantifiers, or require the input or a solution to satisfy an additional condition.