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

### Topology is relevant(in a dichotomy conjecture for infinite-domain CSPs)

#### Joint work with Bodirsky, Olšák, Opršal, Pinsker, Willard.

CSPs...
... of finite structures
... of infinite structures

### Constraint Satisfaction Problems

• $\Bbb A, \Bbb B, \Bbb X$: relational structures
• (Mostly) finite signatures, often infinite domains
CSP($\Bbb A$)
• Input: a finite structure $\Bbb X$,
• Question: is there a homomorphism $\Bbb X\to \Bbb A$?
$h\colon X\to A, (x_1,\dots,x_k)\in R^{\Bbb X}\Rightarrow (h(x_1),\dots,h(x_k))\in R^{\Bbb A}$
• Each problem associated with a relational structure (its template).
• A class of decision problems.
• For a large class of templates, the complexity of each problem depends solely on the symmetries of the template.
$\text{non-trivial symmetries} \leadsto \text{easier problems}$

### Examples

• $\Csp(K_3)$: 3-colourability,
• $\Csp(\{0,1\}; \leq, \{0\},\{1\})$: S-T (non-)reachability,
• $\Csp(\Bbb N; \lt)$: digraph acyclicity.

### History

• 1993: many natural subsets of NP contain NP-intermediate problems, the class of finite-domain CSPs does not seem to be one of them. [Feder-Vardi]
• 2000: All known NP-hard CSPs (with finite-domain) obey a certain algebraic property.
Conjecture: there is an algebraic dividing line between P and NP-hard problems. [Bulatov, Jeavons, Krokhin]
• 2008-2010: several reformulations of the dividing line.
[Maróti-McKenzie, Barto-Kozik, Siggers]
• 2017: Proofs of the algebraic dichotomy conjecture. [Bulatov, Zhuk]

The algebraic method works, what else could it be useful for?
• Promise problems ("hottest" topic),
• Counting,
• Optimisation,
• More decision problems: infinite-domain CSPs.

### Symmetries

• Very symmetric solution spaces are easy to search (systems of linear equations, linear programming over $\Bbb R$),
• Lack of symmetries implies hardness (SAT).
Polymorphism
$\Bbb G=(V,E)$, $f\colon V^n\to V$ is a polymorphism of $\Bbb G$ if
Polymorphisms combine solutions: if $h_1,\dots,h_n\colon \Bbb X\to \Bbb A$ are homomorphisms, $x\mapsto f(h_1(x),\dots,h_n(x))$ is a homomorphism $\Bbb X\to\Bbb A$.
If $\Bbb A$ has good polymorphisms, every instance has a symmetric solution set.

### Algebraic Reductions

Assume we are talking about finite structures.
• $\Pol(\Bbb A)\subseteq\Pol(\Bbb B)$ implies that $\Csp(\Bbb B)$ reduces to $\Csp(\Bbb A)$.
• Only flat identities matter: $g(x,y)= g(y,x), h(x,y)= f(y,y,x), \dots$
If the map preserves flat identities, then $\Csp(\Bbb B)$ reduces to $\Csp(\Bbb A)$.
Bulatov, Jeavons, Krokhin (2000): all known NP-hard finite $\Csp(\Bbb A)$ are such that $\Pol(\Bbb A)\to\Pol(SAT)$.

### The Finite-Domain Dichotomy

Step 1: identify the P/NP-hard borderline
Conjecture (2000) / Theorem (2017)
$\Bbb A$ finite structure. Exactly one of the following holds:
• $\Pol(\Bbb A)\to\Pol(SAT)$ and $\Csp(\Bbb A)$ is NP-complete,
• $\Pol(\Bbb A)\not\to\Pol(SAT)$ and $\Csp(\Bbb A)$ is in P.
Step 2: reformulate the borderline
Theorem
$\Bbb A$ finite structure. Are equivalent:
• $\Pol(\Bbb A)\not\to\Pol(SAT)$
• $\Pol(\Bbb A)$ contains functions that satisfy some nontrivial equations
• $\exists f\in\Pol(\Bbb A)$ s.t. $f(y,x,\dots,x) = f(x,y,x,\dots,x) =\dots = f(x,\dots,x,y)$
• $\exists s\in\Pol(\Bbb A)$ s.t. $s(r,a,r,e) = s(a,r,e,a).$
Infinite-domain CSPs:
• Step 0: identify the scope,
• Step 1: identify the borderline,
• Step 2: find a workable version of the borderline.

### Step 0: Scope

• All infinite-domain CSPs? $\Csp(\Bbb N; Halt, 0, y=x+1)$ is undecidable :(
• Algebraic approach works for $\omega$-categorical templates.
All $\omega$-categorical templates? If P$\neq$ coNP, some $\omega$-categorical CSPs are coNP-intermediate :( :( [Bodirsky, Grohe]
Bodirsky-Pinsker (~2011): structures definable over a finitely bounded homogeneous template ($(\Bbb N;=)$, homogeneous graphs, $(\Bbb Q;\lt)$, ...)
• Contains all finite-domain CSPs,
• All such CSPs are in NP,
• Does not seem to allow for Ladner-like arguments,
• $\omega$-categorical, in particular polymorphisms still capture complexity.

### Step 1: the dividing line

• Complexity still captured by polymorphisms:
$\Pol(\Bbb A)=\Pol(\Bbb B)\Rightarrow$ ptime equivalent CSPs
• If $\exists \xi\colon\Pol(\Bbb A)\to\Pol(SAT)$ uniformly continuous, then $\Csp(\Bbb A)$ is NP-hard.
Conjecture [Barto, Opršal, Pinsker]
$\Bbb A$ definable over a finitely bounded homogeneous structure.
• $\Pol(\Bbb A)\to\Pol(SAT)$ uniformly continuously and $\Csp(\Bbb A)$ is NP-complete,
• $\Pol(\Bbb A)\mathrel{\rlap{\hskip .5em/}}\overset{u.c.}{\longrightarrow}\Pol(SAT)$ and $\Csp(\Bbb A)$ is in P.
Ways to make the conjecture easier to work with:
• Is there a weakest system of nontrivial flat equations for such structures?
• Can topology be dropped in the statement?

### No weakest system of nontrivial flat equations

• Finite undirected graph $\Bbb G\leadsto$ system $\Sigma_{\Bbb G}$ of equations
• $f_1(x,y,z) = g_{1,2}(x,y,x,z,y,z)$
$f_2(x,y,z) = g_{1,2}(y,x,z,x,z,y)$
• $\Bbb G$ not 3-colourable $\Rightarrow \Sigma_{\Bbb G}$ is nontrivial
• Every system $\Sigma$ implies some $\Sigma_{\Bbb G}$
Fact
If $\Bbb A$ contains a triangle and $\Pol(\Bbb A)$ satisfies $\Sigma_{\Bbb G}$, then $\Bbb A$ contains $\Bbb G$.
Theorem [Cherlin, Shelah, Shi]
For every finite connected $\Bbb G$, there exists a nice structure $\Bbb A$ such that $\Bbb X\to\Bbb A$ iff $\Bbb G\mathrel{\rlap{\hskip .5em/}}{\rightarrow} \Bbb X$.
• $\Bbb A$ is definable in a finitely bounded homogeneous structure
• $\Pol(\Bbb A)$ does not satisfy $\Sigma_{\Bbb G}$ ($\Bbb A$ contains a triangle, does not contain $\Bbb G$)
• $\Pol(\Bbb A)$ satisfies some nontrivial flat equations
• $\Csp(\Bbb A)$ is in FO!
Theorem [BMOOPW]
One cannot replace $\Pol(\Bbb A)\mathrel{\rlap{\hskip .5em/}}\overset{u.c.}{\longrightarrow}\Pol(SAT)$ by some equations in the statement of the dichotomy.

### Topology is relevant

Conjecture [Barto, Opršal, Pinsker]
$\Bbb A$ definable over a finitely bounded homogeneous structure.
• $\Pol(\Bbb A)\to\Pol(SAT)$ uniformly continuously and $\Csp(\Bbb A)$ is NP-complete,
• $\Pol(\Bbb A)\mathrel{\rlap{\hskip .5em/}}\overset{u.c.}{\longrightarrow}\Pol(SAT)$ and $\Csp(\Bbb A)$ is in P.
Theorem [BMOOPW]
There exists an $\omega$-categorical structure such that $\Pol(\Bbb A)\mathrel{\rlap{\hskip .5em/}}\overset{u.c.}{\longrightarrow}\Pol(SAT)$ and $\Pol(\Bbb A)\longrightarrow\Pol(SAT)$.
• For each $\Bbb G$ not 3-colorable, $\Bbb A(\Bbb G)$ that does not satisfy $\Sigma_{\Bbb G}$
• Superpose all these structures $\Bbb A:=\Bbb A(\Bbb G_1)\oplus \Bbb A(\Bbb G_2)\oplus\dots$
$\leadsto\Bbb A$ that does not satisfy any $\Sigma_{\Bbb G}$ so $\Pol(\Bbb A)\to\Pol(SAT)$
• $\Pol(\Bbb A)\mathrel{\rlap{\hskip .5em/}}\overset{u.c.}{\longrightarrow}\Pol(SAT)$

### Relevance of topology: what's going on?

• Different but equivalent versions of the dichotomy conjecture:
Conjecture [Bodirsky, Pinsker]
$\Bbb A$ definable over a finitely bounded homogeneous structure.
• $\Pol(\Bbb A)\leadsto\Pol(SAT)$ uniformly continuously and $\Csp(\Bbb A)$ is NP-complete,
• $\Pol(\Bbb A)\mathrel{\rlap{\hskip .3em/}}\overset{u.c.}{\leadsto}\Pol(SAT)$ and $\Csp(\Bbb A)$ is in P.
• This one cares about composition of functions.
• Here topology can be forgotten.