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

Dichotomies in Constraint Satisfaction:
Canonical Functions and Numeric CSPs


Antoine Mottet

CSL 2020

15.01.2020

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$.
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

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]

Overview

CSPs with infinite templates
$(\Bbb Q;\lt)$, $(\Bbb Z; +,\times,1)$, $(\Bbb R;+,\times,\leq)$, ...
Finite-domain CSPs Feder-Vardi conjecture CSPs with ω-categorical templates (temporal reasoning, spatial reasoning, ...) CSPs of reducts of finitely bounded homogeneous structures Bodirsky-Pinsker conjecture Monotone Monadic SNP Reducts of Unary Structures CSPs with numeric templates (linear programming, diophantine equations, ...) CSPs of Presburger-definable templates
Definable in $(\Bbb Z; +, \lt)$
Jonsson-Lööw programme
Disjunctive Linear Diophantine Constraints
Definable in $(\Bbb Z; +, 1)$
Discrete Temporal CSPs
Definable in $(\Bbb Z; \lt)$

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 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$.
Sad observation
In general, $\tilde{\xi}$ is not well-defined.
The homomorphism extension problem has a negative answer.

Positive answers to HEP

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.

Monotone Monadic SNP

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.
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.
[Bodirsky-Madelaine-M., LICS'18]

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