$\def\Csp{\text{CSP}}$ $\def\Pol{\text{Pol}}$ $\def\End{\text{End}}$ $\def\Inv{\text{Inv}}$ $\def\Aut{\text{Aut}}$ $\def\Age{\text{Age}}$

### The Constraint Satisfaction Problem

$D$: finite set.
$\Csp$
• Input: variables $V$, constraints $((z_1,\dots,z_k),R)$
where $z_1,\dots,z_k\in V$, $R\subseteq D^k$
• Question: $\exists h\colon V\to D$ s.t. $(h(z_1),\dots,h(z_k))\in R$ for every constraint?
 $D=\{1,\dots,9\}$: $V=\{x_{1,1},\dots,x_{9,9}\}$ Solutions = Valid sudokus $D=\{0,1\}$: $V=\{x_1,x_2,x_3,x_4\}$ $((x_1,x_2,x_3), R_{000})$ $((x_1,x_2,x_3), R_{111})$ $((x_1,x_2,x_3), R_{011})$ $((x_1,x_3,x_4), R_{001})$ $((x_2,x_3,x_4), R_{000})$ (where $R_{i,j,k}=\{0,1\}^3\setminus\{(i,j,k)\}$). Solution = ?
Complexity? NP-complete (if $|D|>1$).

### More examples

k-colourability
• Input: vertices $V$, edges $E$
• Question: exists proper colouring of $V$ with $k$ colours?
CSP with domain $D=\{1,\dots,k\}$.
Instance: $V=V$, edge $\{v,w\}\leadsto$ constraint $((v,w),\neq)$.
$s$-$t$ Reachability
• Input: vertices $V$, directed edges $E$, $s,t\in V$
• Question: does there exist a path from $s$ to $t$?
Domain: $\{0,1\}$, instance:
• Variables: $V$,
• Constraints: $(v,w)\in E\leadsto ((v,w),\leq)$, $((s),\{1\})$, $((t),\{0\})$
Satisfiable iff no path from $s$ to $t$.
• Restricting the relations allowed in inputs give more precise encodings of problems:
• Sudoku: $R_{All-Diff}(x_1,\dots,x_9)$ and unary singletons,
• 3-SAT $\rightarrow R_{ijk}(x,y,z)$
• colourability $\rightarrow{} \neq$
• $s$-$t$ reachability $\rightarrow{} \leq, \{0\},\{1\}$
$\Csp(D;R_1,\dots,R_p)$
• Input: variables $V$, tuples $((z_1,\dots,z_k),T)$ where $T\,\color{red}{\in \{R_1,\dots,R_p\}}$
• Question: $\exists h\colon V\to D$ s.t. $(h(z_1),\dots,h(z_k))\in T$ for every constraint?
• Complexity depends on $\Bbb A=(D;R_1,\dots,R_p)$
• $\Csp\Biggl($$\Biggr)$ is NP-hard in P NP-hard in P NP-hard NP-hard
• If $D$ allowed to be infinite, every problem is polytime Turing-equivalent to a CSP. [Bodirsky-Grohe '08]
When is $\Csp(D; R_1, \dots, R_p)$ in P? NP-hard? undecidable? ...
• If P$\neq$NP, there are problems in NP, not in P, and not NP-hard [Ladner '75]
• "Finite-domain CSPs do not seem to allow for diagonalization techniques" [Feder, Vardi '93]
Finite-domain CSPs are in P or NP-complete.
Given $\Bbb A$, the question "$\Csp(\Bbb A)$ is in P?" is in NP.
[Bulatov '17, Zhuk '17]
$\Csp\Biggl($ $\Biggr)$ is NP-hard in P NP-hard in P NP-hard NP-hard
What about CSPs with infinite templates?

### Coclones

Observation
If $R\subseteq A^m$ is $\color{red}{\{\exists,\land\}}$-definable in $\Bbb A$, then $\Csp(\Bbb A,R)$ and $\Csp(\Bbb A)$ have the same complexity.
Example:
$\Csp\Biggl($ $\Biggr)$ is NP-hard.
The formula $\phi(x,y):=\exists u,v (E(x,u)\land E(u,v)\land E(v,y))$ defines $x\neq y$.
$\Rightarrow$ reduction from 5-colourability.
$\leadsto$ complexity of $\Csp(\Bbb A)$ determined by the coclone $\langle\Bbb A\rangle$.
$\langle\Bbb A\rangle := \{R\subseteq A^m \mid m\geq 1, R \text{ is } \{\exists,\land\}\text{-definable in } \Bbb A\}$
Study of CSPs = Study of coclones.

### More reductions

• If $\Bbb A$ and $\Bbb B$ are homomorphically equivalent, they have same CSP
• $\psi(x_{1,1},\dots,x_{1,n};\dots;x_{k,1},\dots,x_{k,n})$ defines $k$-ary relation $R$ on $D^n$: $(\underline{a^1},\dots,\underline{a^k})\in R\Leftrightarrow \Bbb A\models \psi(a^1_1,\dots,a^1_n,\dots,a^k_1,\dots,a^k_n)$
• $\Csp(D^n; R)$ reduces to $\Csp(\Bbb A)$.
Example
$\Bbb A=(\{{\color{vermillion}{\bullet}},{\color{green}{\bullet}},{\color{blueish}{\bullet}}\}$, ), $n=3,k=2$, $\psi(x_1,x_2,x_3;y_1,y_2,y_3) := (y_2=x_1\land y_3=x_2\land E(x_3,y_1))$.
Therefore CSP($\vec{C_9}$) reduces to CSP($\vec{C_3}$).
Tractability theorem
If 3-SAT cannot be simulated by powers of $\Bbb A$, then CSP($\Bbb A$) is in P.
[Bulatov FOCS'17, Zhuk FOCS'17]

## Part 1: structures that don't count

### $\omega$-categoricity

$\omega$-categoricity
$\Bbb A$ is $\omega$-categorical if for all $n\geq 1$, there are only finitely many $n$-ary fo-formulas up to equivalence.
Examples:
• $(\Bbb N; =)$: maximal $n$-ary first-order formula $\leftrightarrow$ partition of $\{1,\dots,n\}$
• $(\Bbb Q; \lt)$: weak linear order on $\{1,\dots,n\}$
• Nominal sets: $\left( \binom{\Bbb N}{2}; \{ (S,T) \mid |S\cap T|=1 \} \right)$
• $(\Bbb Z; y=x+1)$: $y=x+1, y=x+2, \dots$
Theorem
For every problem $L$, there exists an $\omega$-categorical $\Bbb A$ such that $L$ reduces to $\Csp(\Bbb A)$, and $\Csp(\Bbb A)$ is in $coNP^L$.
If $P\neq NP$, there is an $\omega$-categorical $\Bbb A$ with a coNP-intermediate CSP.
[Bodirsky-Grohe, ICALP'08]
[Gillibert-Jonušas-Kompatscher-M-Pinsker, '19]

### Polymorphisms: the algebraic approach

$f\colon\Bbb A^n\to\Bbb A$ is a polymorphism of $\Bbb A$ if it preserves every relation of $\Bbb A$. $\Pol(\Bbb A)$ is a clone: it contains projections and is closed under composition.

Theorem
If $\Bbb A$ is $\omega$-categorical, then $\langle\Bbb A\rangle = \Inv(\Pol(\Bbb A))$.
[Geiger '68; Bodnarčuk, Kalužnin, Kotov, Romov '69; Bodirsky, Nešetřil '06]
$\leadsto$ For $\omega$-categorical structures,
Study of CSPs = study of coclones = study of clones.

### Example: Schaefer's dichotomy

Theorem
Let $\Bbb A$ be a structure over $\{0,1\}$. CSP($\Bbb A$) is in P or NP-complete.
[Schaefer, STOC'78]
 If $\Pol(\Bbb A)$ contains... $\langle\Bbb A\rangle$ is contained in... $\min$ $\langle \bigl(\{0,1\}; x\land y\rightarrow z, 0,1\bigr)\rangle$ $\max$ $\langle \bigl(\{0,1\}; \bar x\land \bar y\rightarrow \bar z, 0,1\bigr)\rangle$ $x+y+z$ $\langle \bigl(\{0,1\}; x+y+z=0, x+y+z=1\bigr)\rangle$ majority $\langle 2\text{-SAT}\rangle$
Lemma
If 3-SAT is not simulated by a power of $\Bbb A$, then $\Pol(\Bbb A)$ contains one of the operations above.
[Post, '41]

### Algebraic Hardness

$\xi\colon\mathscr C\to\mathscr D$ is a homomorphism if for all $f\in\mathscr C$ and $\pi_{i_1},\dots,\pi_{i_m}$, we have
$\xi(f\circ (\pi_{i_1},\dots,\pi_{i_m})) = \xi(f)\circ (\pi_{i_1},\dots,\pi_{i_m})$.
$\mathscr P$: clone of projections on $\{0,1\}$.
Theorem
Let $\Bbb A$ be $\omega$-categorical.
If $\Pol(\Bbb A)\to\mathscr P$ is uniformly continuous, then $\Csp(\Bbb A)$ is NP-hard.
[Barto-Opršal-Pinsker '16]
Bodirsky-Pinsker: a dichotomy for all $\omega$-categorical structures is impossible, but some interesting subclass seems to prevent diagonalization techniques.
Conjecture
$\Bbb A$ definable in a finitely bounded homogeneous structure.
If $\Pol(\Bbb A)$ does not unif. continuously maps to $\mathscr P$, then $\Csp(\Bbb A)$ is in P.
[Bodirsky-Pinsker '11; Barto-Opršal-Pinsker '16]
One cannot remove uniform continuity from the statement.
[Bodirsky-M.-Olšak-Opršal-Pinsker-Willard, LICS'19]

### Canonical Functions

$\overline a\sim_{\Bbb B} \overline b$: $\exists\alpha\in\Aut(\Bbb B) : \alpha(\overline a)=\overline b$.
If $\Bbb B$ is $\omega$-categorical, $\sim_{\Bbb B}$ has finite index for all length of tuples.
Canonical function
$f\colon B^n\to B$ is canonical with respect to $\Bbb B$ if it preserves $\sim_{\Bbb B}$.
If $\Bbb A$ is definable in $\Bbb B$, then $\Aut(\Bbb B) \subseteq \Pol(\Bbb A,\sim_{\Bbb B}) \subseteq \Pol(\Bbb A)$.
Theorem
$\Bbb A$ definable in a finitely bounded homogeneous structure $\Bbb B$.
If $\Pol(\Bbb A,\sim_{\Bbb B})$ has no uniformly continuous homomorphism to $\mathscr P$, then $\Csp(\Bbb A)$ is in P.
[Bodirsky-M., LICS'16]
• The Bodirsky-Pinsker conjecture holds for clones of canonical functions.
• Unification of several tractability results.

### The Homomorphism Extension Problem

Recall:
• If $\Pol(\Bbb A,\sim_{\Bbb B})\not\rightarrow\mathscr P$, $\Csp(\Bbb A)$ is in P.
• If $\Pol(\Bbb A)\rightarrow\mathscr P$, $\Csp(\Bbb A)$ is NP-hard.
Homomorphism Extension Problem
Let $\xi\colon\Pol(\Bbb A,\sim_{\Bbb B})\rightarrow\mathscr P$ be a uniformly continuous homomorphism. Does $\xi$ admit a uniformly continuous extension $\Pol(\Bbb A)\rightarrow\mathscr P$?
Theorem
Suppose that $\Bbb B$ is a Ramsey structure. Let $f\colon B^n\to B$.
Then $\exists g\in\overline{\Aut(\Bbb B)f\Aut(\Bbb B)}$ canonical with respect to $\Bbb B$.
[Bodirsky-Pinsker-Tsankov '12]
A solution to the homomorphism extension problem..?
• Assume $\xi\colon\Pol(\Bbb A,\sim_{\Bbb B})\rightarrow\mathscr P$ is a homomorphism.
• For $f\in\Pol(\Bbb A)$, define $\tilde{\xi}(f)$ to be $\xi(g)$, where $g$ is a canonical friend of $f$.
In general, $\tilde{\xi}$ is not well-defined.
The homomorphism extension problem has a negative answer.

Theorem
The Homomorphism Extension Problem has a positive answer in the following cases:
• Reducts of unary structures: the mashup technique, [Bodirsky-M., LICS'16]
• MMSNP: hybrid relational approach. [Bodirsky-Madelaine-M., LICS'18]
Open problem
Classify the structures $\Bbb B$ for which HEP has a positive answer.

Input: a finite graph $G$,
Question: can $G$ be colored with and in a way to avoid monochromatic triangles?
Complexity: NP-complete.
Input: a finite graph $G$,
Question: can $G$ be colored with and in a way to avoid the following patterns?
Complexity: in P.
• Coloring problems with forbidden patterns.
• No-mono-triangle is not a finite-domain CSP.
Theorem
Every finite-domain CSP can be seen as such a coloring problem.
Every coloring problem is ptime equivalent to a finite-domain CSP.
[Feder-Vardi '93; Kun '13]
Observation
Every coloring problem is $\Csp(\Bbb A)$ for some $\Bbb A$ in the Bodirsky-Pinsker class.
[Bodirsky-Dalmau '12]
Theorem
The Homomorphism Extension Problem has a positive answer for the MMSNP structures.
• The Bodirsky-Pinsker conjecture is true for CSPs in MMSNP.
• New proof of the Feder-Vardi-Kun result.

## Part 2: structures that count

### Structures with semilinear relations

Jonsson-Lööw Programme
Classify the complexity of all CSPs of templates $(\Bbb Z; R_1,\dots,R_p)$ where $R_1,\dots,R_p$ are definable in Presburger arithmetic $(\Bbb Z; +, \leq, 1)$.
• Difference logic: $(\Bbb Z; \{\{(x,y) \mid y-x\leq c\} \mid c\in\Bbb Z\})$ $\begin{cases}x-y &\leq 4\\ y-z &\leq 5\\ z-x &\leq -10\end{cases}$
• Solving linear diophantine equations: $(\Bbb Z; x+y=z, 1)$
• Max-Atoms: $(\Bbb Z; x\leq\max(y,z), y=x+1)$ $\begin{cases}x &\leq \max(y+1,z-1)\\ y &\leq \max(z,t)\\ t &\leq x\end{cases}$
• Solving mean-payoff games!

### Mean-Payoff Games Value of run $e_1,e_2,\dots$: $\liminf_{n} \frac1n\sum_{i=1}^n w(e_i)$
$P$ wins if against every adversary, the value of every run is positive
Mean-Payoff Games
Input: a finite game $G$,
Question: does P win?
Theorem
Mean-payoff games is ptime equivalent to $\Csp(\Bbb Z; x\leq\max(y,z), y=x+1,y=x+2,\dots)$ with constants encoded in binary.
[Atserias-Maneva, '09]
Note: $(\Bbb Z; x\leq\max(y,z), y=x+1,y=x+2,\dots)$ is definable in $(\Bbb Z;\lt)$.

### Results

Theorem
Let $\Bbb A$ be definable in $(\mathbb Z;\lt)$.
Then $\Csp(\Bbb A)$ is in P or NP-complete and the meta-problem is decidable.
[Bodirsky-Martin-M., ICALP'15]
[Bodirsky-Dalmau-Martin-M.-Pinsker, Information and Computation 2016]
[Bodirsky-Martin-M., Journal of the ACM 2018]
Question: what about structures definable in $(\Bbb Z; \lt, 0)$?
Includes all finite-domain CSPs.
Theorem
Let $\Bbb A$ be definable in $(\mathbb Z;+,1)$ and contain $+$ in its language.
Then $\Csp(\Bbb A)$ is in P or NP-complete and the meta-problem is decidable.
[Bodirsky-Mamino-Martin-M., MFCS'18]
Question: what about structures that don't contain $+$?

### Conclusion

• CSPs with $\omega$-categorical templates:
• New tools for the study of clone homomorphisms and canonical functions,
• Generalisable methods towards a solution of the
Bodirsky-Pinsker conjecture,
• New, algebraic proof of foundational result by Feder and Vardi.
• CSPs with numeric templates:
• First systematic classifications in the Jonsson-Lööw programme,
• New techniques ($\omega$-saturation),
• Alternative approach to parity games/mean payoff games?