# On the Maximum Constraint Satisfaction Problem

Johan Thapper (LIX)An instance of the maximum constraint satisfaction problem (Max CSP) is specified by a set of variables, a domain, and a set of constraints. Each constraint imposes a relation over the domain on a subset of variables. The relations are chosen from a fixed set called the constraint language. The goal is to find an assignment of domain values to the variables that satisfies as many constraints as possible. The question is: Given a fixed constraint language, what is the computational complexity of Max CSP?

Until not long ago, all evidence pointed to, and it was conjectured that

- Max CSP is tractable whenever the constraint language is supermodular with respect to a lattice; and
- This is essentially the only source of tractability for Max CSP.

I will present recent results showing that (1) is correct and that (2) is false.

The talk is based on joint work with Peter Jonsson, Fredrik Kuivinen, and Stanislav Zivny.