Topology is relevant

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

Antoine Mottet

LICS 2019

26.06.2019

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.