ALGA 2016

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

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

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

33-colorability

33-colorability

33-colorability

Linear Equations mod 22

33-SAT

Constraint Satisfaction Problems

FO-definable Structures

FO-definable Structures

Homomorphism Problem

Definable 33-colorability

Decidable

Definable Linear Equations mod 22

Decidable

Homomorphism Problem

Finite Relations

Finite Signature

$3$ -colorability

$3$ -colorability

$3$ -colorability

Linear Equations mod $2$

$3$ -SAT

Definable $3$ -colorability

Definable Linear Equations mod $2$