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.
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.
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 Bodirsky-Pinsker conjecture holds for clones of canonical functions.
Unification of several tractability results.
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]
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.
Coloring problems with forbidden patterns.
No-mono-triangle is not a finite-domain CSP.
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]
The Bodirsky-Pinsker conjecture is true for CSPs in MMSNP.
New proof of the Feder-Vardi-Kun result.
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)$.
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
CSPs with $\omega$-categorical templates:
New tools for the study of clone homomorphisms and canonical functions,
Generalisable methods towards a solution of the Bodirsky-Pinsker conjecture,
New, algebraic proof of foundational result by Feder and Vardi.
CSPs with numeric templates:
First systematic classifications in the Jonsson-Lööw programme,
New techniques ($\omega$-saturation),
Alternative approach to parity games/mean payoff games?