Homomorphism Problems for First-Order Definable Structures


joint work with Bartek Klin, Eryk Kopczyński, Sławek Lasota and Szymon Toruńczyk


Joanna Ochremiak


ALGA, Marseille, 12th April 2016

Homomorphisms


Problem: Hom$(\mathbb{B})$

Input: structure $\mathbb{A}$ (over the same signature)

Decide: Is there a homomorphism from $\mathbb{A}$ to $\mathbb{B}$?







$3$-colorability


$3$-colorability


$3$-colorability


Linear Equations mod $2$


$\mathbb{B} = \bigl( \{0,1\}, R_1, R_0 \bigr)$


$R_0 = \{ (x,y,z) \in \{0,1 \}^3 \ | \ x+y+z=0 \mbox{ mod } 2\}$

$R_1 = \{ (x,y) \in \{0,1 \}^2 \ | \ x+y=1 \mbox{ mod } 2\}$


$$\begin{align*} x+y+z=0 \\ x+y=1 \end{align*}$$

$\mathbb{A} = \bigl( \{x,y,z\}, R_0(x,y,z), R_1(x,y) \bigr)$


$3$-SAT


$\mathbb{B} = \bigl( \{0,1\}, R_{000}, R_{100}, R_{110}, R_{111} \bigr)$


$R_{000} = \{0,1 \}^3 \setminus \{(0,0,0) \}$

$R_{100} = \{0,1 \}^3 \setminus \{(1,0,0) \}$

$R_{110} = \{0,1 \}^3 \setminus \{(1,1,0) \}$

$R_{111} = \{0,1 \}^3 \setminus \{(1,1,1) \}$

$$\begin{align*} \neg x \wedge y \wedge z \end{align*}$$

$\mathbb{A} = \bigl( \{x,y,z\}, R_{100}(x,y,z) \bigr)$


Constraint Satisfaction Problems


CSP Dichotomy Conjecture (Feder, Vardi). For every finite structure $\mathbb{B}$, the problem Hom$(\mathbb{B})$ is solvable in polynomial time or NP-complete.


We study CSP for infinite structures (related to the work of Bodirsky et al.).

FO-definable Structures


$\{ 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

FO-definable Structures


$\{ 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

Homomorphism Problem


Problem: Hom$(\mathbb{B})$

Input: definable structure $\mathbb{A}$ (over the same signature)

Decide: Is there a homomorphism from $\mathbb{A}$ to $\mathbb{B}$?







Theorem. There exists a definable structure $\mathbb{B}$ for which the problem Hom$(\mathbb{B})$ is undecidable.

Definable $3$-colorability


Decidable

Definable Linear Equations mod $2$



$\begin{align*} x_{ab} + x_{ba} &= 1, \mbox{ where $a$ and $b$ are distinc} \\ x_{ab}+x_{bc}+x_{ca} &=0, \mbox{where $a$, $b$ and $c$ are distinct} \end{align*}$



Decidable

Homomorphism Problem


Problem: Hom$(\mathbb{B})$

Input: definable structure $\mathbb{A}$ (over the same signature)

Decide: Is there a homomorphism from $\mathbb{A}$ to $\mathbb{B}$?







Theorem. There exists a definable structure $\mathbb{B}$ for which the problem Hom$(\mathbb{B})$ is undecidable.

Finite Relations


Theorem. If $\mathbb{B}$ is a definable structure whose every relation is finite, then Hom$(\mathbb{B})$ is decidable.


Theorem. For a finite structure $\mathbb{B}$, if Hom$(\mathbb{B})$ is C-complete for finite input structures, then Hom$(\mathbb{B})$ is Exp(C)-complete for definable input structures.


$3$-colorability of definable graphs is NEXP-complete.

Finite Signature


Theorem. If $\mathbb{B}$ is a definable structure over a finite signature, then Hom$(\mathbb{B})$ is decidable.

Proof techniques: Ramsey theory, topological dynamics

Generalizations: other atoms; both structures as input

Applications: TMA, descriptive complexity


Open problem: isomorphism of definable structures