Question: Can we assign values to variables so that all the constraints are satisfied?

Complexity of CSP

A CSP template $\Gamma$ is a set of types of constraints.

Problem: CSP$(\Gamma)$

Input: CSP instance with constraints from $\Gamma$

Decide: Is there an assignment satisfying all the constraints?

CSP Dichotomy Conjecture. For every finite template $\Gamma$, the problem CSP$(\Gamma)$ is solvable in polynomial time or NP-complete.

Max-cut

Goal: Find a coloring with minimal cost.

Valued CSP

Valued CSP

Goal: Find an assignment with minimal cost.

$2$-colorability

Goal: Find a coloring with minimal cost.

Complexity of VCSP

Problem: VCSP$(\Gamma)$

Input: VCSP instance with (valued) constraints from $\Gamma$

Goal: Find an assignment with minimal cost.

VCSP Dichotomy Conjecture. For every finite set of types of (valued) constraints $\Gamma$, the problem VCSP$(\Gamma)$ is solvable in polynomial time or NP-hard.

Theorem (Kozik, O.). If Pol$^+(\Gamma)$ does not have a cyclic operation, then VCSP$(\Gamma)$ is NP-hard.

$3$-colorability

Question: Can we color this graph?

$3$-colorability

Question: Can we color this graph?

FO-definable Instance

$\{ ab \ | \ a,b \in \mathbb{A}, a \neq b \}$ - vertices

$\{ \{ab,bc\} \ | \ a,b,c \in \mathbb{A}, a \neq b \wedge b \neq c \wedge a \neq c \}$ - edges

Definable CSP

Definable CSP

Problem: def-CSP$(\Gamma)$

Input: FO-definable CSP instance over $\Gamma$

Decide: Is there an assignment satisfying all the constraints?

A template $\Gamma$ is locally finite if every constraint allows only finitely many values for each variable.

Theorem (Klin, Kopczyński, O., Toruńczyk). If $\Gamma$ is locally finite, then def-CSP$(\Gamma)$ is decidable.

TM with Atoms

Turing machine with atoms is a Turing machine whose alphabet, state space, and transition relation are FO-definable sets.

Standard Alphabets

An alphabet $\mathcal{A}$ is standard iff every language $\mathcal{L}$ over $\mathcal{A}$ recognisable by a nondeterministic TMA is recognisable by some deterministic TMA.

Theorem (Bojańczyk, Klin, Lasota, Toruńczyk). There exists a non-standard alphabet.

Theorem (Klin, Lasota, O., Toruńczyk). An alphabet $\mathcal{A}$ is standard iff a CSP template $\Gamma_{\mathcal{A}}$ has a
majoritypolymorphism.

Polymorphisms

A function $f \colon D^k \rightarrow D$ is a polymorphism of a relation $R \subseteq D^n$ if

Theorem (Bulatov, Krokhin, Jeavons). If every polymorphism of $\Gamma$ is a polymorphism of $R$, then CSP$(\Gamma \cup \{R \})$ is polynomial-time reducible to CSP$(\Gamma)$.

Theorem (Cohen, Cooper, Creed, Jeavons, Živný). If every weighted polymorphism of $\Gamma$ is a weighted polymorphism of $R$, then VCSP$(\Gamma \cup \{R \})$ is polynomial-time reducible to VCSP$(\Gamma)$.

Weighted polymorphisms characterize the complexity of VCSP.

Let $R \ \colon \ D^n \rightarrow \mathbb{Q} \cup \{\infty\}$ be a weighted relation.

A weighted polymorphism of $R$ is a probability distribution $\omega$ on the set of $m$-ary functions such that for any $n$-tuples ${\bf x_1}, \dots, {\bf x_m}$, such that $R({\bf x_i}) < \infty$,
$$\sum_{g \ \in \ supp(\omega)} \omega(g) R(g({\bf x_1},\dots,{\bf x_m})) \leq {1\over m} (R({\bf x_1})+\dots+R({\bf x_m})),$$
where $supp(\omega)$ is the set of operations to which $\omega$ assigns a positive probability.