A Story of Oligomorphic Clones
and Finite Minions
AAA 105
01/06/2024
Antoine Mottet (TU Hamburg)
CSPs with Finite Templates
Universal algebra $\leftrightarrow$ Constraint Satisfaction
In this talk, "structure" means relational structure $\mathbb A=(A;R_1,\dots,R_k)$
$\Hom(\mathbb A)$ is the problem:
- Input: $\mathbb X$, finite
- Question: does there exist a homomorphism $\mathbb X\to\mathbb A$?
same as defining the set of yes-instances $\Hom(\mathbb A)=\{\mathbb X\mid \mathbb X \text{ finite structure s.t. } \mathbb X\to\mathbb A\}$
- Many natural classes are of the form $\Hom(\mathbb A)$: graphs with chromatic number at most $k$, graphs with clique number at most $k$, acyclic digraphs, ...
- Complexity of $\Hom(\mathbb A)\; =$ complexity of deciding membership of a given $\mathbb X$ in such classes
- One can have $\mathbb A$ infinite. Sometimes it must be infinite.
The class of finite loopless graphs is $\Hom(\mathbb K_\infty)$, where $\mathbb K_\infty$ is the countable complete graph.
If $\{\text{finite loopless graphs}\}\subseteq\Hom(\mathbb A)$ and $\mathbb A$ has fewer than $n$ vertices, then since $K_n$ is loopless and $K_n\to\mathbb A$, $\mathbb A$ must contain a loop, so $\Hom(\mathbb A)$ contains all finite graphs.
If $\{\text{finite loopless graphs}\}\subseteq\Hom(\mathbb A)$ and $\mathbb A$ has fewer than $n$ vertices, then since $K_n$ is loopless and $K_n\to\mathbb A$, $\mathbb A$ must contain a loop, so $\Hom(\mathbb A)$ contains all finite graphs.
Universal algebra $\leftrightarrow$ Constraint Satisfaction
$\Hom(\mathbb A)$ is the problem:
- Input: $\mathbb X$, finite
- Question: does there exist a homomorphism $\mathbb X\to\mathbb A$?
same as defining the set of yes-instances $\Hom(\mathbb A)=\{\mathbb X\mid \mathbb X \text{ finite structure s.t. } \mathbb X\to\mathbb A\}$
If $f\in\Pol(\mathbb A)$, $f\colon \mathbb A^n\to\mathbb A$ and $h_1,\dots,h_n\colon \mathbb X\to\mathbb A$, then $f\circ (h_1,\dots,h_n)\colon \mathbb X\to\mathbb A$.
polymorphisms can be used to combine solutions / restrict solution space
$\Longrightarrow$ The structure of $\Pol(\mathbb A)$ can be used to study $\Hom(\mathbb A)$
[Schaefer, '78]
Let $\mathbb A$ have domain $\{0,1\}$. Then $\Hom(\mathbb A)$ is:
- solvable in P if $\Pol(\mathbb A)$ contains operations that are not essentially unary,
- and $\Hom(\mathbb A)$ is NP-complete otherwise.
Proof by case distinction: for each of the 6 minimal clones containing a non-essentially unary operation, find a polynomial-time algorithm
CSPs with Finite Domains
1978
1990
1993
1998
2000
2002
2003
2005
2008
2010
2012
2016
2017
[Schaefer]
Let $\mathbb A$ have domain $\{0,1\}$. Then $\Hom(\mathbb A)$ is:
- solvable in P if $\Pol(\mathbb A)$ contains operations that are not essentially unary,
- and $\Hom(\mathbb A)$ is NP-complete otherwise.
[Hell-Nešetřil]
Let $\mathbb A$ be a finite undirected graph. Then $\Hom(\mathbb A)$ is:
- solvable in P if $\mathbb A$ is bipartite or has a loop,
- and $\Hom(\mathbb A)$ is NP-complete otherwise.
[Feder, Vardi]
$\Hom(\mathbb A)$ is always solvable in polynomial time or NP-complete.[Jeavons]
Complexity of $\Hom(\mathbb A)$ is completely determined by $\Pol(\mathbb A)$ when $\mathbb A$ is finite.[Bulatov, Krokhin, Jeavons]
The complexity of $\Hom(\mathbb A)$ only depends on the equational variety generated by $\Pol(\mathbb A)$.$\Hom(\mathbb A)$ is NP-hard if $\Pol(\mathbb A)$ is not Taylor.*
Proof based on primitive positive interpretations:
- if $\mathbb B$ is of the form $(S/{\sim}, T_1,\dots,T_\ell)$ where $S\subseteq A^d,{\sim}\subseteq S^2,T_1,\dots,T_\ell$ are all pp-definable in $\mathbb A$, then $\Hom(\mathbb B)$ reduces to $\Hom(\mathbb A)$
- this is true of $\mathbb B$ iff there exists a clone homomorphism $\Pol(\mathbb A)\to\Pol(\mathbb B)$
Alternatively, iff the polymorphism algebra of $\mathbb B$ is in the variety generated by that of $\mathbb A$ - So if $\Pol(\mathbb A)\to\Pol(\mathbb B)$, then $\Hom(\mathbb B)\leq\Hom(\mathbb A)$
[Barto, Opršal, Pinsker]
Complexity of $\Hom(\mathbb A)$ only depends on the height 1 identities satisfied by $\Pol(\mathbb A)$.
A height 1 identity is a statement of the form $$f(\text{variables}) \approx g(\text{variables})$$
Proof based on primitive positive constructions: pp-interpretations + homomorphic equivalence
If $\Pol(\mathbb A)$ is idempotent and Taylor then it contains:
- a weak near-unanimity operation of some arity $k\geq 3$ $$f(x,x,\dots,x,y)\approx f(x,x,\dots,y,x)\approx\dots\approx f(x,y,\dots,x,x)\approx f(y,x,\dots,x,x)$$
- a $6$-ary $f$ satisfying $f(x,y,x,z,y,z)\approx f(y,x,z,x,z,y).$
- cyclic operations of all prime arities $>|A|$ $$f(x_1,x_2,\dots,x_n)\approx f(x_2,x_3,\dots,x_n,x_1)$$
[Maróti, McKenzie] [Siggers] [Barto, Kozik]
Last two statements based on loop lemmas, absorption theory
[Bulatov]
If $\Pol(\mathbb A)$ has a Mal'tsev operation, then $\Hom(\mathbb A)$ is solvable in polynomial time.[Bulatov]
If $A$ has size 3 and $\Pol(\mathbb A)$ is Taylor, then $\Hom(\mathbb A)$ is solvable in polynomial time.
Like Schaefer, based on case analysis
If $\Pol(\mathbb A)$ is conservative and Taylor, then $\Hom(\mathbb A)$ is solvable in polynomial time.
[Bulatov]
If $\mathbb A$ is a finite smooth digraph, then $\CSP(\mathbb A)$ is in P when it has a weak near-unanimity polymorphism, and it is NP-complete otherwise.
[Barto, Kozik, Niven]
[Idziak, Markovic, McKenzie, Valeriote, Willard]
If $\Pol(\mathbb A)$ has few subpowers, then $\Hom(\mathbb A)$ is solvable in polynomial time.
[Bulatov // Zhuk]
$\Hom(\mathbb A)$ is in P when $\Pol(\mathbb A)$ is idempotent and not equationally trivial.So we know everything there is to know about $\Hom(\mathbb A)$ when $\mathbb A$ is finite,*** nice! What's next?
- CSPs with $\omega$-categorical templates / Oligomorphic Clones
- Promise CSPs / Minions
- Some questions
- How they relate
- Some answers
CSPs with $\omega$-categorical templates
Infinite CSPs and Oligomorphic Clones
No hope to understand all CSPs in general.
Restrict to $\CSP(\mathbb A)$ where $\Pol(\mathbb A)$ is well-behaved.
Restrict to $\CSP(\mathbb A)$ where $\Pol(\mathbb A)$ is well-behaved.
A clone $\Pol(\mathbb A)$ on $A$ is oligomorphic if all the finite powers $A^n$ are finitely generated already under the invertible unary operations.
Equivalently, the group $\Aut(\mathbb A)$ acts with finitely many orbits on every $A^n$.
- Finite $A$
- $\Pol(\mathbb A) \supseteq $ all permutations on $\mathbb Q$, or all monotone permutations on $\mathbb Q$
- $\Pol(\mathbb A) \supseteq$ automorphism group of a homogeneous structure (like $(\mathbb Q;<)$ or the Rado graph)
Consequences:
- Finitely many $\Pol(\mathbb A)$-invariant subsets of $A^n$ for all $n$.
- By compactness/induction arguments, can recover some properties that hold for finite clones (Pol-Inv correspondence).
- Define $f \sim g$ iff for every finite $S\subseteq A$, there exists $\alpha\in\mathcal G$ such that $\alpha f|_S=g|_S$.
Then $(A^{A^n})/{\sim}$ is compact for all $n$. - Corresponds to $\mathbb A$ being $\omega$-categorical. [Ryll-Nardzewski, Engeler, Svenonius]
Infinite-domain CSPs
2003
2006
2008
2011
2015
2016
2018
2019
2020
2021
2022
2023
2024
Suppose $\Pol(\mathbb A)$ is oligomorphic. Then:
- $R\subseteq A^n$ is invariant under $\Pol(\mathbb A)$ iff it is pp-definable in $\mathbb A$
- If $\Pol(\mathbb A)$ and $\Pol(\mathbb B)$ are topologically isomorphic, then $\CSP(\mathbb A)$ and $\CSP(\mathbb B)$ are equivalent.
[Bodirsky, Nešetřil] [Bodirsky, Pinsker]
[Barto, Pinsker]
Let $\mathcal G$ be an oligomorphic group on $A$ and let $\mathbb A=(A;E)$ be an undirected graph such that $\Aut(\mathbb A)\supseteq\mathcal G$ and containing a triangle.
Then:
- $\mathbb A$ together with orbits of $\mathcal G$ and parameters pp-interprets every finite structure, or
- $E$ contains a pseudoloop, a pair $(a,\alpha(a))$ for some $\alpha\in\mathcal G$.
$\Longrightarrow$ if $\Pol(\mathbb A)$ is nontrivial, then it satisfies the pseudo-Siggers identity $$u\circ f(x,y,x,z,y,z)\approx v\circ f(y,x,z,x,z,y)$$ with $u,v\in\overline{\Aut(\mathbb A)}$.*
[Barto, Bodor, Kozik, M., Pinsker]
Let $\mathcal G$ be an oligomorphic group on $A$ and let $\mathbb A=(A;E)$ be a smooth digraph such that $\Aut(\mathbb A)\supseteq\mathcal G$, where $\mathbb A/{\mathcal G}$ is symmetric and contains a triangle.
Then:
- $\mathbb A$ together with orbits of $\mathcal G$ and parameters pp-interprets every finite structure, or
- $E$ contains a pseudoloop, a pair $(a,\alpha(a))$ for some $\alpha\in\mathcal G$.
There is no weakest strong height 1 condition for oligomorphic polymorphism clones:
given any finite $\Sigma$, there exists an oligomorphic $\Pol(\mathbb A)$ that does not satisfy $\Sigma$ but satisfies $$f(x,x,\dots,x,y)\approx f(x,x,\dots,y,x)\approx f(x,y,\dots,x,x)\approx f(y,x,\dots,x)\approx f(x,\dots,x)$$ for some arity.
given any finite $\Sigma$, there exists an oligomorphic $\Pol(\mathbb A)$ that does not satisfy $\Sigma$ but satisfies $$f(x,x,\dots,x,y)\approx f(x,x,\dots,y,x)\approx f(x,y,\dots,x,x)\approx f(y,x,\dots,x)\approx f(x,\dots,x)$$ for some arity.
[Bodirsky, M., Olšák, Opršal, Pinsker, Willard]
[Bodirsky, Grohe] [Gillibert, Jonušas, Kompatscher, M., Pinsker]
- $\Hom(\mathbb A)$ where $\Pol(\mathbb A)$ is oligomorphic is still very wild (CSPs of all* possible complexities).
- Complexity not captured by equations (even by being very permissive with the notion of "capture" and "equations").
[Bodirsky, Kára]
Let $\mathbb A$ be such that $\Pol(\mathbb A)$ contains the full symmetric group. Then $\Hom(\mathbb A)$ is:
- solvable in P if $\Pol(\mathbb A)$ contains an injective operation or a constant,
- and $\Hom(\mathbb A)$ is NP-complete otherwise.
[Bodirsky, Kára]
Let $\mathbb A$ be such that $\Pol(\mathbb A)$ contains the group of order-preserving permutations of $\mathbb Q$.
Then $\Hom(\mathbb A)$ is:
- solvable in polynomial time if $\Pol(\mathbb A)$ contains one of 9 operations,
- and $\Hom(\mathbb A)$ is NP-complete otherwise.
Relies on a classification of all the possible $\Aut(\mathbb A)$.
[Bodirsky, Pinsker]
Let $\mathbb A$ be such that $\Pol(\mathbb A)$ contains the group of automorphisms of the Rado graph.
Then $\Hom(\mathbb A)$ is:
- solvable in polynomial time if $\Pol(\mathbb A)$ contains one of 17 operations,
- and $\Hom(\mathbb A)$ is NP-complete otherwise.
Relies on a prior classification of all the possible $\Aut(\mathbb A)$.
[Bodirsky, Pinsker]
Let $\mathbb A$ be a reduct of a finitely bounded homogeneous structure.
Then $\Hom(\mathbb A)$ is in P whenever $\mathbb A$ does not pp-interpret with parameters all finite structures.*
Assumption implies:
- $\mathbb A$ is $\omega$-categorical / $\Pol(\mathbb A)$ is oligomorphic
- $\Hom(\mathbb A)$ is in NP
[Bodirsky, Martin, Pinsker, Pongrácz]
Let $\mathbb A$ be such that $\Aut(\mathbb A)$ contains the group of automorphisms of any homogeneous undirected graph.
Then $\Hom(\mathbb A)$ is:
- solvable in P if $\Pol(\mathbb A)$ contains ...,
- and $\Hom(\mathbb A)$ is NP-complete otherwise.
Relies on a prior classification of all the possible $\Aut(\mathbb A)$
AND all the possible homogeneous undirected graphs.
AND all the possible homogeneous undirected graphs.
[Kompatscher, Van Pham]
Let $\mathbb A$ be such that $\Aut(\mathbb A)$ is the group of automorphisms of the universal homogeneous poset.
Then $\Hom(\mathbb A)$ is:
- solvable in P if $\Pol(\mathbb A)$ contains one of 2 operations,
- and $\Hom(\mathbb A)$ is NP-complete otherwise.
For $m$ large enough, define $\Gamma_m\colon \mathbb A=(A;R_1,\dots,R_k) \mapsto \Gamma_m\mathbb A$ structure on $A^m$ with:
Then $\Hom(\mathbb A)$ reduces in polynomial time to $\Hom(\Gamma_m\mathbb A/{\mathcal G})$.
- unary relations encoding $R_1,\dots,R_k$
- binary relations specifying equalities between $m$-tuples
[Bodirsky, M.]
Let $\mathbb A$ be a reduct of a finitely bounded homogeneous structure with automorphism group $\mathcal G$.Then $\Hom(\mathbb A)$ reduces in polynomial time to $\Hom(\Gamma_m\mathbb A/{\mathcal G})$.
- $\Pol(\Gamma_m\mathbb A/{\mathcal G})$ essentially the same as $\Pol(\mathbb A,\Theta_{\mathcal G})$, where $(a,b)\in\Theta_{\mathcal G}$ iff $a,b\in A^m$ are in the same orbit under $\mathcal G$
- If $\Pol(\Gamma_m\mathbb A/{\mathcal G})$ is non-trivial, then $\Hom(\Gamma_m\mathbb A/{\mathcal G})$ is solvable in polynomial time.
$\Rightarrow$ does away with the need for case distinctions for the algorithms (in many cases)! - $\Pol(\mathbb A)$ can be non-trivial and $\Pol(\mathbb A,\Theta_{\mathcal G})$ trivial
E.g. if $\mathcal G=\Aut(\mathbb Q;<)$
[Bodirsky, M.] [M., Pinsker] [M., Nagy, Pinsker, Wrona] [M., Nagy, Pinsker]
Let $\mathbb A$ be ⟨any of the previous mentioned structures and many more⟩.
Then $\Hom(\mathbb A)$ is:
- solvable in polynomial time if $\Pol(\mathbb A)$ is equationally non-trivial,
- and $\Hom(\mathbb A)$ is NP-complete otherwise.
Smooth Approximations:
- Relate the non-existence of non-trivial identities satisfied in $\Pol(\mathbb A,\Theta_{\mathcal G})$ to the fact that $\Pol(\mathbb A)$ obeys a "pseudoloop lemma" that gives binary operations satisfying strong properties
- Eliminates the need for establishing a list of "minimal good polymorphisms"
- Eliminates the need for classification of groups $\Aut(\mathbb A)$
- Also works if one is interested at other equational conditions:
characterization of bounded width structures when $\Aut(\mathbb A)$ contains a particular fixed group* - Works best under some structure conditions (primitivity, no algebraicity), flow needs to be adapted in other cases
- Still a few ad hoc arguments
On the algebra side:
- Pattern: $\Pol(\mathbb A,\Theta_{\mathcal G})$ is non-trivial, or $\Pol(\mathbb A)$ is trivial, or $\Pol(\mathbb A)$ contains interesting binary operations*
- Height 1 Identities modulo a group seem to be important and in particular the pseudo-Siggers identity $$u\circ f(x,y,x,z,y,z)\approx v\circ f(y,x,z,x,z,y)$$
Understand the structure of $\Pol(\mathbb A)$ better whenever
$\mathbb A$ does not pp-construct/interpret all finite structures.
$\mathbb A$ does not pp-construct/interpret all finite structures.
On the CSP side:
- "Reduction to the finite" powerful, but not enough for certain groups (e.g., $\Aut(\mathbb Q;<)$)
- Algorithmic aspects still need to be better understood (e.g., CSPs over $(\mathbb Q;<)$)
- For "well-behaved" structures (reducts of finitely bounded homogeneous structures),
$\Hom(\mathbb A)$ is conjectured to be in P whenever $\mathbb A$ does not pp-construct all finite structures
Find generic algorithms solving infinite-domain CSPs
Promise CSPs with Finite Templates
Promise CSPs
$\mathbb A, \mathbb B$ structures with $\mathbb A\to\mathbb B$.
$\PCSP(\mathbb A,\mathbb B)$ is the problem of determining, given $\mathbb X$, whether
$\PCSP(\mathbb A,\mathbb B)$ is the problem of determining, given $\mathbb X$, whether
- Yes: there exists a homomorphism $\mathbb X\to\mathbb A$
- No: there does not exist a homomorphism $\mathbb X\to\mathbb B$
Since $\mathbb A\to\mathbb B$, at most one case is possible.
We are promised that at least one is true.
We are promised that at least one is true.
- $\mathbb {OIT}=(\{0,1\}, \{(1,0,0),(0,1,0),(0,0,1)\})$ vs. $\mathbb{NAE}_2=(\{0,1\}, \{0,1\}^3\setminus\{(0,0,0),(1,1,1)\})$
Solvable in polynomial time! - $\PCSP(\mathbb K_a,\mathbb K_b)$ for $a\leq b$
Conjectured to be NP-hard for all $a\leq b$ (known e.g. for $a=3\leq b\leq 5$)
Does not pp-construct $\mathbb K_3$ in general.
About PCSPs
- Complexity determined by polymorphisms $\mathbb A^n\to\mathbb B$
$\Pol(\mathbb A,\mathbb B)$ is a minion: set of functions closed under minors
if $f\colon \mathbb A^n\to \mathbb B$ is a polymorphism and $\sigma\colon\{1,\dots,n\}\to\{1,\dots,m\}$, $f^{\sigma}(x_1,\dots,x_m) := f(x_{\sigma(1)},\dots,x_{\sigma(n)})$
is a polymorphism. - $\PCSP(\mathbb A,\mathbb B)$ is equivalent to the following problem (for some constant $N$):
Given $\Sigma$ a set of height 1 identities about functions of arity at most $N$, decide whether- Yes: the identities are satisfied by projections on a 2-element set
- No: the identities are not satisfiable in $\Pol(\mathbb A,\mathbb B)$
- $(\mathbb C,\mathbb D)$ pp-constructible in $(\mathbb A,\mathbb B)$ iff $\Pol(\mathbb A,\mathbb B)\to\Pol(\mathbb C,\mathbb D)$
Implies $\PCSP(\mathbb C,\mathbb D)\leq \PCSP(\mathbb A,\mathbb B)$. - Hardness not well understood
(every year comes with a stronger kind of hardness proof + proof that previous techniques are not enough) - Fertile ground for new algorithms feeding back into world of finite-domain CSPs
Basic Linear Programming relaxation (BLP) and Affine Integer Programming relaxation (AIP)
Bounded Width and Finite Tractability
- $\mathbb X$ is locally consistent w.r.t. $\mathbb A$ if no contradiction can be derived by looking at constant-sized subsets of $\mathbb X$ and propagating implied constraints
- $(\mathbb A,\mathbb B)$ has bounded width if every $\mathbb X$ that is locally consistent w.r.t. $\mathbb A$ admits a homomorphism to $\mathbb B$
- Makes sense for CSPs as well (with $\mathbb A=\mathbb B$)
- If $\mathbb A$ finite, then $\mathbb A$ has bounded width iff $\Pol(\mathbb A)$ contains WNU of all arities [Larose, Zádori] [Maróti, McKenzie] [Barto, Kozik]
Classify the finite PCSP templates $(\mathbb A,\mathbb B)$ that have bounded width.
Classify the $\omega$-categorical structures $\mathbb A$ that have bounded width.
Classify the $\omega$-categorical structures $\mathbb A$ that have bounded width.
- $(\mathbb A,\mathbb B)$ is finitely tractable if there exists a finite $\mathbb C$ such that $$\mathbb A\to\mathbb C\to\mathbb B$$ such that $\Hom(\mathbb C)$ is solvable in polynomial time
- The template $(\mathbb{OIT}, \mathbb{NAE}_2)$ is not finitely tractable, although the PCSP is solvable in polynomial time [Barto]
Classify the finite PCSP templates $(\mathbb A,\mathbb B)$ that are finitely tractable.
Are there finite PCSP templates that are not finitely tractable but such that there exists a tractable $\omega$-categorical $\mathbb C$?
Are there finite PCSP templates that are not finitely tractable but such that there exists a tractable $\omega$-categorical $\mathbb C$?
Oligomorphic clones and finite minions
CSPs over $(\mathbb Q;<)$ revisited
[M.]
Let $\mathbb B$ be such that $\Aut(\mathbb B)\supseteq\Aut(\mathbb Q;<)$ and $\mathbb A$ finite such that $\mathbb A\to\mathbb B$.Suppose that $\CSP(\mathbb B)$ is not NP-hard.
Then $\PCSP(\mathbb A,\mathbb B)$ is solvable by local consistency + singleton AIP.
[M., Pinsker]
Let $\mathbb B$ be such that $\Aut(\mathbb B)\supseteq\Aut(\mathbb Q;<)$.
Suppose that $\CSP(\mathbb B)$ is not NP-hard.
Then $\Pol(\mathbb B)$ contains some function $f$ preserving $\theta:=(x=0\Leftrightarrow y=0)$ on $\mathbb Q_{\geq 0}$ and such that $f/{\theta}$ is either a semilattice or a minority operation.
Based on a pseudoloop lemma: every $\emptyset\neq R\subseteq \mathbb Q^2$ invariant under $\Pol(\mathbb B)$ contains a pseudo-loop modulo $\Aut(\mathbb Q;<,0)$.
$\Rightarrow$ Let $\mathbb A\subseteq\mathbb B$ be finite and $\theta$ isolate the minimal element of $\mathbb A$.
Then $\Pol(\mathbb A/{\theta})$ is a Boolean clone with a semilattice or minority operation.
Let $\mathbb X$ be an input that is locally consistent and passes the singleton AIP test as an instance of $\CSP(\mathbb A)$.
Wlog $\mathbb A\subseteq\mathbb B$. Let $\theta$ be the congruence on $\mathbb A$ isolating the minimal element $a$.
Wlog $\mathbb A\subseteq\mathbb B$. Let $\theta$ be the congruence on $\mathbb A$ isolating the minimal element $a$.
- $\mathbb X$ is locally consistent/has singleton AIP witnesses for $\mathbb A/{\theta}$
- Consistency+AIP witnesses the existence of a nontrivial homomorphism $h\colon\mathbb X\to\mathbb A/{\theta}$
- Repeat previous step on $\mathbb X\setminus h^{-1}(a)$*
- "New" algorithm for $\Hom(\mathbb B)$ when $\Aut(\mathbb B)\supseteq\Aut(\mathbb Q;<)$!
- (Re)moves an important obstacle: the need for ad hoc algorithms solving CSPs over $(\mathbb Q;<)$.
- Algorithm is uniform and does not depend on $\Pol(\mathbb B)$
- Only the proof of correctness uses polymorphisms
Oligomorphic clones as limits of finite minions
For $m$ large enough, define $\Gamma_m\colon \mathbb A=(A;R_1,\dots,R_k) \mapsto \Gamma_m\mathbb A$ structure on $A^m$ with:
- unary relations encoding $R_1,\dots,R_k$
- binary relations specifying equalities between $m$-tuples
Let $\mathcal G$ be a subgroup of $\Aut(\mathbb B)$.
A map $\xi\colon\mathcal M\to\Pol(\mathbb A,\mathbb B)$ is a $\mathcal G$-weak minion homomorphism if for every height 1 identity $f(\text{vars})= g(\text{vars})$ in $\mathcal M$, the identity $u\circ \xi(f)(\text{vars})=v\circ\xi(g)(\text{vars})$ holds for some $u,v\in\overline{\mathcal G}$.
[M.]
Let $\mathcal G\subseteq\Pol(\mathbb A)$ be oligomorphic.
Then $\Pol(\mathbb A)$ is the $\mathcal G$-weak projective limit of
$$\require{AMScd}\minCDarrowwidth5pt\begin{CD}
\dots @>>> \Pol(\Gamma_{m+1}\mathbb A_{i+1},\Gamma_{m+1}\mathbb A/{\mathcal G}) @>>> \Pol(\Gamma_{m+1}\mathbb A_{i},\Gamma_{m+1}\mathbb A/{\mathcal G}) @>>> \Pol(\Gamma_{m+1}\mathbb A_{i-1},\Gamma_{m+1}\mathbb A/{\mathcal G}) @>>> \dots\\
@. @VVV @VVV @VVV @.\\
\dots @>>> \Pol(\Gamma_m\mathbb A_{i+1},\Gamma_m\mathbb A/{\mathcal G}) @>>> \Pol(\Gamma_m\mathbb A_{i},\Gamma_m\mathbb A/{\mathcal G}) @>>> \Pol(\Gamma_m\mathbb A_{i-1},\Gamma_m\mathbb A/{\mathcal G}) @>>> \dots
\end{CD}
$$
$$\require{AMScd}\minCDarrowwidth5pt\begin{CD}
\dots @>>> \Pol(\Gamma_{m+1}\mathbb A_{i+1},\Gamma_{m+1}\mathbb A/{\mathcal G}) @>>> \Pol(\Gamma_{m+1}\mathbb A_{i},\Gamma_{m+1}\mathbb A/{\mathcal G}) @>>> \dots\\
@. @VVV @VVV @.\\
\dots @>>> \Pol(\Gamma_m\mathbb A_{i+1},\Gamma_m\mathbb A/{\mathcal G}) @>>> \Pol(\Gamma_m\mathbb A_{i},\Gamma_m\mathbb A/{\mathcal G}) @>>> \dots
\end{CD}
$$
where $\mathbb A_i$ are finite substructures of $\mathbb A$ such that $\mathbb A_1\subseteq\mathbb A_2\subseteq\dots\subseteq \bigcup\mathbb A_i=\mathbb A$ and $m\in\mathbb N$.If $\mathcal G$ is the automorphism group of a finitely bounded homogeneous structure, then $m$ can be fixed large enough.
Oligomorphic clones as limits of finite minions
- If $\mathcal G$ is the automorphism group of a finitely bounded homogeneous structure, $\Hom(\mathbb A)$ is equivalent to $\PCSP(\Gamma_m\mathbb A,\Gamma_m\mathbb A/{\mathcal G})$ (for some $m\in\mathbb N$)
- The height 1 identities that hold in $\Pol(\mathbb A)$ modulo $\mathcal G$ are those that hold in every $\Pol(\Gamma_m\mathbb A_i,\Gamma_m\mathbb A/{\mathcal G})$.
- $\mathcal M$ be the free minion generated by identity
- If $\mathcal M\to(\Gamma_m\mathbb A_i,\Gamma_m\mathbb A/{\mathcal G})$ for all $m, i$ then $\mathcal M\color{red}{\to}\Pol(\mathbb A)$ by previous result
- If $\mathbb A$ does not pp-construct $(\mathbb K_3,\mathbb K_r)$, then $\Pol(\mathbb A)$ contains a pseudo-Siggers operation.
- $(\Gamma_m\mathbb A_i,\Gamma_m\mathbb A/{\mathcal G})$ does not pp-construct $(\mathbb K_3,\mathbb K_r)$ for all $m, i$
- $\Pol(\Gamma_m\mathbb A_i,\Gamma_m \mathbb A/{\mathcal G})$ contains a Siggers operation [Barto, Bulín, Krokhin, Opršal]
- If $\mathbb A$ does not pp-construct $(\mathbb{NAE}_2,\mathbb{NAE}_r)$, then $\Pol(\mathbb A)$ contains a pseudo-Olšák operation $$u\circ f(x,x,y,y,y,x) \approx v\circ f(x,y,x,y,x,y)\approx w\circ f(y,x,x,x,y,y).$$
- If $\mathbb A$ has bounded width, $\Pol(\mathbb A)$ contains pseudo weak near-unanimity operations of all arities [Atserias, Dalmau] $$u_1\circ f(x,x,\dots,x,y)\approx u_2\circ f(x,x,\dots,y,x)\approx\dots\approx u_{k-1}\circ f(x,y,\dots,x,x)\approx u_k\circ f(y,x,\dots,x,x).$$
$\omega$-categorical CSPs and sandwiches
[M.]
There exists a PCSP template $(\mathbb A,\mathbb B)$ such that:
- $(\mathbb A,\mathbb B)$ has bounded width,
- $(\mathbb A,\mathbb B)$ is not finitely tractable,
- $(\mathbb A,\mathbb B)$ is not solvable by BLP+AIP,
- There exists an $\omega$-categorical $\mathbb C$ such that $\mathbb A\to\mathbb C\to\mathbb B$ and $\CSP(\mathbb C)$ is solvable in polynomial time.
Same holds with "solvable by singleton AIP" instead of bounded width.
Open problems
- Characterize pp-constructibility for $\omega$-categorical structures
- Weak minion homomorphisms helpful?
Probably not for complexity considerations - Polymorphism clone of $\omega$-categorical structure $\rightsquigarrow$ "projective" limit of system of finite minions
Given a directed system of finite minions, when can one define a "projective" limit that is a clone? - Infinite CSPs equivalent to a problem about equational conditions?
- Generic algorithms for CSPs with $\omega$-categorical templates
$\rightsquigarrow$ understand tractability - Push the theory of smooth approximations further (imprimitivity, algebraicity, general theory underlying the use of the "loop lemma of smooth approximations")
$\rightsquigarrow$ understand hardness
Thank you for your attention!
/