## Homomorphisms

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

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

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

## 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 Linear Equations mod $2$

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

## 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