Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction

Fixed-template Constraint Satisfaction Problems are computational problems parametrized by structures $𝔄$ with a finite relational signature, called templates; they are denoted by $\mathrm{CSP}(𝔄)$ and ask whether a given structure $𝔍$ with the same signature as $𝔄$ admits a homomorphism to $𝔄$. The general CSP framework is incredibly rich, in fact, it contains all decision problems up to polynomial-time equivalence [20]. For this reason, CSPs are typically studied under additional structural restrictions on the template $𝔄$. The restriction that has received most attention is requiring the domain of $𝔄$ to be finite, and the problems arising in this way are called finite-domain CSPs. Already in this setting, one obtains many well-known problems such as HORN-SAT, 2-SAT, 3-SAT, or 3-COLORING.

Consider the example of 3-COLORING. This NP-complete problem can be modeled as $\mathrm{CSP}({𝔎}_3)$, where ${𝔎}_3$ stands for the complete graph on three vertices: indeed, a homomorphism to ${𝔎}_3$ from a given structure $𝔍$ in the same signature (i.e. from a graph $𝔍$) is simply a mapping that does not map any two adjacent vertices of $𝔍$ to the same vertex of ${𝔎}_3$. A key observation in the theory of CSPs is that the NP-completeness of $\mathrm{CSP}({𝔎}_3)$ can be extended to CSPs of other structures which can “simulate” ${𝔎}_3$ over their domain or over a finite power thereof using primitive positive (pp) formulas. Enhancing this by the additional observation that homomorphically equivalent templates have equal CSPs, one arrives at the notion of pp-constructibility [9]. If ${𝔄}^{\prime }$ is pp-constructible from $𝔄$, then $\mathrm{CSP}({𝔄}^{\prime })$ is reducible to $\mathrm{CSP}(𝔄)$ in logarithmic space; moreover, this reduction can be formulated in the logic programming language Datalog. This uniform reduction between CSP templates is sufficiently powerful, as we will see below, to describe all NP-hardness amongst finite-domain CSPs.

In the early 2000s, the field of finite-domain constraint satisfaction quickly rose in fame, in particular due to the discovery of tight connections with universal algebra. The most basic of these connections is that two structures with identical domains have the same sets of pp-definable relations if and only if they have the same sets of polymorphisms [52, 51]. Here, a polymorphism of a relational structure $𝔄$ is simply a homomorphism from a finite power of $𝔄$ into $𝔄$ itself; we denote by $\mathrm{Pol}(𝔄)$ the set of all polymorphisms of $𝔄$, the polymorphism clone of $𝔄$. Since taking expansions by pp-definable relations does not lead to an increase in complexity, the study of finite-domain CSPs is subsumed by the study of finite algebras. Over the past two decades, the link between universal algebra and CSPs was gradually refined. After an intermediate stop at pp-interpretations [37], today we know that also pp-constructibility between finite relational structures is fully encoded in their polymorphisms [9, Theorem 1.3]: ${𝔄}^{\prime }$ is pp-constructible from $𝔄$ if and only if $\mathrm{Pol}({𝔄}^{\prime })$ satisfies all height-1 identities of $\mathrm{Pol}(𝔄)$. By a breakthrough result of Bulatov [36] and Zhuk [68, 69], the pp-construction of ${𝔎}_3$ is the unique source of NP-hardness for finite-domain CSPs (if P$\ne$NP), and in fact, they provided a polynomial-time algorithm for any such CSP which does not pp-construct ${𝔎}_3$. Besides its complexity-theoretic significance (in particular, of confirming the dichotomy conjecture of Feder and Vardi [44]), this result has the additional appeal that the border for tractability can be described by a neat universal-algebraic condition on polymorphism clones. We state the theorem of Bulatov and Zhuk in a formulation which takes into account the results in [9] and [66].

Arguably, the two main reasons for the popularity of finite-domain CSPs over CSPs which require an infinite template are immediate containment of such problems in the class NP (a homomorphism can be guessed and verified in polynomial time) as well as the above-mentioned applicability of algebraic methods which had been developed independently of CSPs for decades. Yet, even within the class NP, finite-domain CSPs are of an extremely restricted kind: already simple problems such as ACYCLICITY of directed graphs (captured by the template ), various natural coloring problems for graphs such as NO-MONOCHROMATIC-TRIANGLE, and more generally the model-checking problem for natural restrictions of existential second-order logic such as the logic MMSNP of Feder and Vardi [44], are beyond its primitive scope despite their containment in NP.

The quest for a CSP framework including such problems whilst staying within NP and allowing for an algebraic approach akin to the one for finite templates started with the popularization of $\omega$-categoricity by Bodirsky and Nešetřil [27] as a sufficient structural restriction ensuring the latter: for countable $\omega$-categorical structures, pp-definability is determined by their polymorphisms and, as was subsequently shown, so are the general reduction of pp-interpretability [29] as well as the pp-constructibility of ${𝔎}_3$ [9]. The $\omega$-categoricity of $𝔄$ can be interpreted as $𝔄$ being “finite modulo automorphisms”: more precisely, the action of its automorphism group $\mathrm{Aut}(𝔄)$ on $d$-tuples has only finitely many orbits for all finite $d\ge 1$. It is, however, a mathematical property with little computational bearing: the CSPs of $\omega$-categorical structures can be monstrous from this perspective [49, 48] (complete for a variety of complexity classes of arbitrarily high complexity). For this reason, and based on strong empirical evidence, Bodirsky and Pinsker [31] identified a proper subclass of countable $\omega$-categorical structures as a candidate for an algebraic complexity dichotomy extending the theorem of Bulatov and Zhuk which does not seem to suffer from this deficiency.

Their first requirement on $𝔄$ is that the orbit under $\mathrm{Aut}(𝔄)$ of any $d$-tuple is determined by the relations that hold on it: we call a relational structure $𝔄$ homogeneous if every isomorphism between its finite substructures extends to an automorphism of $𝔄$. This gives an effective way of representing orbits, which are central to $\omega$-categoricity. They then additionally impose an effective way of determining whether a given finite substructure is contained in $𝔄$, which places the CSP in NP: a relational structure $𝔄$ over a finite signature $\tau$ is finitely bounded [55] if there exists a finite set $𝒩$ of finite $\tau$-structures (bounds) such that a finite $\tau$-structure embeds into $𝔄$ if and only if it does not embed any member of $𝒩$; equivalently, the finite substructures are up to isomorphism precisely the finite models of some universal first-order sentence [14, Lemma 2.3.14] (see also [25, 64] for more details).

Finite boundedness and homogeneity taken together is a very strong assumption. Bodirsky and Pinsker observed that for all practical purposes, in particular the applicability of polymorphisms to complexity as well as containment in NP, it is sufficient that the template $𝔄$ be a first-order reduct of a structure $𝔅$ enjoying these, i.e. first-order definable therein. This yields sufficient flexibility to model a huge class of computational problems which includes in particular the ones mentioned above. In fact, requiring $𝔄$ to be a reduct of a finitely bounded homogeneous structure $𝔅$, i.e. obtained from $𝔅$ by forgetting relations, turns out to be equivalent [3, Proposition 7], and we shall find this approach convenient.

The following formulation of the conjecture takes into account later progress [9, 10, 11, 7].

It is important to note that the open part of Conjecture 4 is only the consequence of polynomial-time tractability: the negation of the first item does yield the satisfaction of the pseudo-Siggers identity by a theorem due to Barto and Pinsker [11]. It is even equivalent to it for model-complete cores [7, Theorem 1.3]: an $\omega$-categorical model-complete core is a template $𝔄$ whose endomorphisms preserve all orbits of $\mathrm{Aut}(𝔄)$; it exists for all CSPs with an $\omega$-categorical template and is unique up to isomorphism [13].

Conjecture 4 has been confirmed for many subclasses. Mottet and Pinsker speak of first- and second-generation classifications [60]: those of the former kind can roughly be described as exhaustive case-by-case analyzes, using Ramsey theory, of the available polymorphisms for the first-order reducts of a fixed finitely bounded homogeneous structure $𝔅$ – extensive complexity classifications such as those for temporal CSPs [22], Graph-SAT problems [28], Poset-SAT problems [54], and CSPs with templates first-order definable in arbitrary homogeneous graphs [24] were obtained this way. Second-generation classifications take a more structured approach mimicking advanced algebraic methods for finite domains; they were employed, for example, to achieve classifications for the logic MMSNP [23], Hypergraph-SAT problems [59], and certain graph orientation problems [45, 12]. However, even the most advanced methods as described in [60] require additional abstract structural assumptions on the template.

One such assumption is that the template $𝔄$, or even the structure $𝔅$ in which it is first-order defined, has no algebraicity. It is present virtually everywhere in the infinite-domain CSP literature [23]; and in particular an important prerequisite in most of the general results of the theory of smooth approximations developed by Mottet and Pinsker [60], as well as in all results of Bodirsky and Greiner [18, 19] about CSPs of generic superpositions of theories. We say that a structure $𝔄$ has no algebraicity (in the group-theoretic sense) if, for every $k\ge 1$ and every $\overline{a}\in A^k$, the automorphisms of $𝔄$ which stabilize $\overline{a}$ do not stabilize any $a^{\prime }\notin \overline{a}$ (i.e. $a^{\prime }$ does not appear as an entry of $\overline{a}$). In $\omega$-categorical structures this is the case if and only if, for every $k\ge 1$, every tuple $\overline{a}\in A^k$, and every $a^{\prime }\notin \overline{a}$, it is not possible to first-order define the unary relation $\{a^{\prime }\}$ using $\overline{a}$ as parameters; in other words, any non-trivial first-order property relative to $\overline{a}$ is always satisfied by infinitely many elements, which implies that some arguments become easier compared to finite structures (whereas naturally, many other arguments become harder). We will show that the following strengthening of this property (for model-complete cores, see Proposition 13) can be assumed when resolving Conjecture 4: a structure $𝔄$ is CSP-injective if every finite structure that homomorphically maps to $𝔄$ also does so injectively; in other words, if there is a solution to an instance of $\mathrm{CSP}(𝔄)$, then there is also an injective one. CSP-injectivity played an essential role in the universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP [23] and, more recently, certain finitely bounded homogeneous uniform hypergraphs [59].

One of the properties preserved by our construction enforcing CSP-injectivity in Theorem 6 below is that of the structure $𝔅$ being Ramsey. Although of central importance in classification methods [30, 62], its precise definition is not essential to the present paper and therefore omitted; we refer the reader to [50] for details about structural Ramsey theory.

Throughout the present paper, the notation $𝔄\wr 𝔅$ stands for the relational wreath product of two structures $𝔄$ and $𝔅$, introduced formally in Section 4.1, and ${𝔄}_R$ stands for the expansion of a structure $𝔄$ by a relation $R$ defined over its domain.

It is not hard to see that item 4 of Theorem 6 applies to reducts of homogeneous structures in a finite relational signature [55], in particular to all structures in the scope of Conjecture 4.

Comparing Theorem 1 with Conjecture 4, one notices the replacement of the Siggers identity by its (weaker) pseudo-variant. This is not just an inconvenience arising from the proof of Barto and Pinsker in [11] (or the more recent proof in [5]), but there are examples showing the necessity to weaken the condition.

We say that a template is Pol-injective if all of its polymorphisms are essentially injective, i.e. injective up to dummy variables – this is the case if and only if the relation $I_4$ is invariant under its polymorphisms. As it turns out, the relation $I_4$ can be added to the templates constructed in Theorem 6 at no computational cost (up to Datalog reductions). It thus follows that any algebraic condition on polymorphisms capturing a complexity class closed under Datalog-reductions for CSPs of structures within the scope of Conjecture 4 must necessarily be satisfiable by essentially injective operations. Until now, various concrete examples of natural templates all of whose polymorphisms are essentially injective had pointed towards a statement of this kind (see e.g. [7]); we provide a rigorous confirmation.

For finite structures the only essentially injective polymorphisms are at most unary up to dummy variables. It is therefore of no surprise that so few universal-algebraic conditions for CSPs from the finite have been successfully lifted to the infinite. One prominent example which can actually be lifted is the satisfiability of quasi near-unanimity identities, which captures bounded strict width both in the finite and in the infinite [16]; bounded strict width corresponds to solvability in a particular proper fragment of Datalog that is not closed under the Datalog-reductions in Theorem 6. Examples of conditions for polymorphism clones that can be satisfied by essentially injective operations are any pseudo height-1 identities (e.g., the pseudo-Siggers identity), but also the dissected near-unanimity identities [48] which were proposed in [32] as a possible candidate for solvability of CSPs in fixed-point logic.

Marimon and Pinsker have recently provided a negative answer, within the scope of Conjecture 4, to a question of Bodirsky [14, Question 14.2.6(27)] asking whether every $\omega$-categorical CSP template without algebraicity which is solvable in Datalog has a binary injective polymorphism [56, Corollary 8.10]. We contrast this negative result with a corollary to Theorem 8 that implies that up to Datalog reductions the answer is positive.

One of the currently most vibrant branches of research in constraint satisfaction are Promise Constraint Satisfaction Problems (PCSPs). For two relational structures ${𝔖}_1$ and ${𝔖}_2$ such that ${𝔖}_1$ maps homomorphically to ${𝔖}_2$, the problem $\mathrm{PCSP}({𝔖}_1,{𝔖}_2)$ asks to decide whether a given finite structure $𝔍$ in the same signature as ${𝔖}_1$ and ${𝔖}_2$ maps homomorphically to ${𝔖}_1$ or does not even map homomorphically to ${𝔖}_2$; the instance $𝔍$ is promised to satisfy one of those two cases. Thus, the problem $\mathrm{PCSP}({𝔖}_1,{𝔖}_2)$ asks to compare $\mathrm{CSP}({𝔖}_1)$ to a relaxation $\mathrm{CSP}({𝔖}_2)$ of it, and since $\mathrm{PCSP}({𝔖}_1,{𝔖}_1)=\mathrm{CSP}({𝔖}_1)$, promise constraint satisfaction problems generalize the CSP framework. This generalization is vast, and contains many well-known computational problems such as APPROXIMATE GRAPH COLORING [46], $(2+\epsilon )$-SAT [2], and HYPERGRAPH COLORING [41]. Although formally not necessary, research has focused on finite templates $({𝔖}_1,{𝔖}_2)$: this is justified for example by the fact that even for structures over a Boolean domain, there is no complete complexity classification yet. Hence, the two extensions considered here of finite-domain CSPs to $\omega$-categorical templates, or alternatively to PCSPs, are somewhat orthogonal, and it is natural to wonder whether there exist any connections, in particular of algorithmic nature.

One potential link is the use of $\omega$-categorical CSP templates as cheeses in the sandwich method to prove tractability of PCSPs, as follows. Note that if $𝔄$ is a structure such that ${𝔖}_1$ maps homomorphically to $𝔄$ and $𝔄$ maps homomorphically to ${𝔖}_2$, then $\mathrm{PCSP}({𝔖}_1,{𝔖}_2)$ trivially reduces to $\mathrm{CSP}(𝔄)$; we call $𝔄$ a cheese sandwiched by the template $({𝔖}_1,{𝔖}_2)$. This simple observation is more powerful than it might first appear: in fact, so far, every known tractable (finite-domain) PCSP can be reduced to the tractable CSP of some cheese structure via the sandwich method [57, 40]. On the other hand, Barto [4] provided an example of a PCSP template sandwiching an infinite polynomial-time tractable cheese while not being finitely tractable, i.e. such that every finite-domain cheese has an NP-complete CSP [4]. Since Barto’s cheese is not $\omega$-categorical, he raised the question whether such an example could also be constructed with an $\omega$-categorical cheese ([4, Question IV.1]). Subsequently the question arose, and was promoted in particular by Zhuk at the CSP World Congress 2023, whether structures within the scope of Conjecture 4 could ever serve as tractable cheeses in the absence of a finite one. The first two examples of tractable $\omega$-categorical cheeses for non-finitely tractable finite-domain PCSPs were recently obtained by Mottet [58]; his structures fall within the scope of Conjecture 4. In the present paper, we strengthen this result by creating non-finitely tractable finite-domain PCSPs from virtually every structure $𝔄$ within the scope of Conjecture 4. Our construction consists of two steps. First, we show that such a construction is possible in general under the additional assumption that $𝔄$ is equipped with an inequality predicate and that it is a reduct of a structure $𝔅$ which is linearly ordered. We then combine this construction with Theorem 6. Modulo an extra step consisting of taking generic superpositions (Proposition 18) of structures with (for which we need the property of no algebraicity), this finishes our proof.

The last item in Theorem 10 is not necessary for obtaining non-finitely tractable PCSPs from Conjecture 4, but provides an additional link that makes it possible to transfer logical inexpressiblity results from infinite-domain CSPs to PCSPs. For example, the PCSPs provided by the theorem from $\mathrm{CSP}(\mathbb{Q};X)$, where , will not be solvable in Fixed-Point logic with Counting (FPC), because $\mathrm{CSP}(\mathbb{Q};X)$ is not [32] and the instances witnessing the inexpressiblity in FPC homomorphically map to $(\mathbb{Q};X)$ if and only if they homomorphically map to a fixed finite substructure of it (cf. [58, Proposition 37]). We expect a similar situation for the PCSPs associated with the first-order reducts of the homogeneous $C$-relation [21], due to the recent work [67, Theorem 4.7].

Our results compare to the above-mentioned examples of Mottet [58, Propositions 35 and 36] of a tractable $\omega$-categorical cheese for a finite-domain PCSP that is not finitely tractable as follows. First, Mottet’s finite-domain PCSPs [58, Theorem 2] are reducible to the associated $\omega$-categorical templates under gadget reductions, which are the specific form of Datalog-reductions stemming from pp-constructions. The main advantage of gadget reductions over general Datalog-reductions is that, in many settings, gadget reductions between (P)CSPs are captured by the transfer of height-1 identities between polymorphism clones (or more generally polymorphism minions); see [39]. As a trade-off for the generality of our result (Theorem 10), our Datalog-reductions are not given in terms of gadgets; in fact, one can formally prove that, in many cases, our finite-domain PCSPs do not admit a gadget reduction to the original $\omega$-categorical template (Example 15). Second, Mottet’s work [58] also contains a result (Theorem 1) showing that every CSP within the scope of the Bodirsky-Pinsker conjecture is polynomial-time equivalent to the PCSP of a half-infinite template, more precisely a template $({𝔖}_1,{𝔖}_2)$ such that ${𝔖}_1$ is in the scope of the Bodirsky-Pinsker conjecture and ${𝔖}_2$ is finite. In contrast, our Theorem 10 provides non-finitely tractable finite-domain PCSP templates $({𝔖}_1,{𝔖}_2)$ sandwiching a given structure $𝔄$ from Conjecture 4 up to Datalog interreducibility. Since our PCSP templates $({𝔖}_1,{𝔖}_2)$ are finite and not half-infinite, we cannot guarantee polynomial-time equivalence between $\mathrm{PCSP}({𝔖}_1,{𝔖}_2)$ and $\mathrm{CSP}(𝔄)$. However, our construction still allows us to approximate $\mathrm{CSP}(𝔄)$ to an arbitrary degree in the sense of item 7 in Theorem 10.

Given groups $G$ and $H$ acting on sets $A$ and $B$, respectively, their wreath product $G\wr H$ is given by $G^B\times H$ acting on $A\times B$ via $({(g_b)}_{b\in B},h))(a,b)≔(g_{h(b)}(a),h(b)).$ The wreath product $G\wr H$ again forms a group, with the neutral element $({(e_G)}_{b\in B},e_H)$ and the group operation $({(g_b)}_{b\in B},h))\cdot ({(g_b^{\prime })}_{b\in B},h^{\prime }))≔({(g_b\cdot g_{h^{-1}(b)}^{\prime })}_{b\in B},h\cdot h^{\prime }))$. Note that the permutation group on $A\times B$ induced by the component-wise action of the Cartesian product $G\times H$ is contained by that induced by the action of $G\wr H$ thereon: the permutations induced stemming from the former are represented in $G\wr H$ by all elements of the form $({(g)}_{b\in B},h)$.

Below we give an important construction on structures (here also called wreath product) which corresponds to group-theoretic wreath products in terms of their automorphism groups. Let $𝔄$ and $𝔅$ be structures over disjoint relational signatures $\tau$ and $\sigma$, and let $E$ be a fresh binary symbol. The wreath product $𝔄\wr 𝔅$ is the structure over the signature $\tau \cup \{E\}\cup \sigma$ with domain $A\times B$ whose relations are defined as follows. First, set $E^{𝔄\wr 𝔅}≔\{((x_1,y_1),(x_2,y_2))\in {(A\times B)}^2\mid y_1=y_2\}$. Then, for $R\in \tau$ and $S\in \sigma$ of arities $k$ and $m$:

Proofs of items 4, 5, and 6 can be found in [33, Lemma 2.2.49] (see also [34, Lemma 2.33]). The statement in item 6 can also be found in [65, Theorem 5.13].

In the context of Conjecture 4, the concepts of CSP-injectivity and having no algebraicity are closely related. On the one hand, if $𝔅$ is a homogeneous structure with no algebraicity and its relations only contain tuples with pairwise distinct entries, then it is CSP-injective [14, Lemma 4.3.6]. On the other hand, we can prove the following.

We shall now see that CSP-injectivity and Pol-injectivity cannot hold simultaneously in $\omega$-categorical structures; yet, we shall observe immediately thereafter that CSP-injectivity can be traded against Pol-injectivity using the relation $I_4$ from Example 5.

Our basic tool for creating $\omega$-categorical cheeses for PCSPs that are not finitely tractable are full powers (see, e.g., Bodirsky [14, Section 3.5]). Roughly speaking, a full power ${𝔄}^{[d]}$ is a higher-dimensional representation of $𝔄$ that can be pp-constructed from it and vice versa; its central feature is that its polymorphisms are the polymorphisms of $𝔄$ acting on $d$-tuples, thus allowing to factor it by the orbit-equivalence of $\mathrm{Aut}(𝔄)$ on $d$-tuples (rather than on elements). In other words, the orbits of $d$-tuples of $𝔄$ are represented by orbits of $1$-tuples of ${𝔄}^{[d]}$, which is crucial in applications of the sandwich method. Let $𝔄$ be a relational structure with a signature $\tau$ and let $d\in \mathbb{N}$ be arbitrary. The $d$-th full power of $𝔄$, denoted ${𝔄}^{[d]}$, is the structure with domain $A^d$ and the following relations for every $k\in [d]$:

• $\mathrm{■}$

  for every $R\in \tau$ of arity $k$ and every injection $\iota :[k]\to [d]$, the unary relation

  $R_{\iota }^{{𝔄}^{[d]}}≔\{(a_1\mathrm{\dots },a_d)\in A^d\mid (a_{\iota (1)},\mathrm{\dots },a_{\iota (k)})\in R^{𝔄}\};$

• $\mathrm{■}$

  for every $R\in \tau$ of arity $k$ and every function $\iota :[k]\to [d]$, the $k$-ary relation

  ${\widehat{R}}_{\iota }^{{𝔄}^{[d]}}≔\{((a_1^1,\mathrm{\dots },a_d^1),\mathrm{\dots },(a_1^k,\mathrm{\dots },a_d^k))\in {(A^d)}^k\mid (a_{\iota (1)}^1,\mathrm{\dots },a_{\iota (k)}^k)\in R^{𝔄}\};$

• $\mathrm{■}$

  for all functions $\iota ,{\iota }^{\prime }:[k]\to [d]$, the binary compatibility relation

  $S_{\iota ,{\iota }^{\prime }}^{{𝔄}^{[d]}}≔\{((a_1^1\mathrm{\dots },a_d^1),(a_1^2,\mathrm{\dots },a_d^2))\in {(A^d)}^2\mid \forall i\in [k]:a_{\iota (i)}^1=a_{{\iota }^{\prime }(i)}^2\}.$

Below we give several important properties of full powers.

To construct a finite PCSP sandwich for a structure $𝔄$, we must only select a finite substructure ${𝔖}_1$ and a finite factor ${𝔖}_2$ of $𝔄$. The issue is that, in many cases, $\mathrm{PCSP}({𝔖}_1,{𝔖}_2)$ will be finitely tractable, possibly because already $\mathrm{CSP}({𝔖}_1)$ or $\mathrm{CSP}({𝔖}_2)$ is tractable. Proposition 17 describes a general condition for structures in the scope of Conjecture 4 under which this does not happen, i.e., where $\mathrm{PCSP}({𝔖}_1,{𝔖}_2)$ is provably not finitely tractable. Intuitively, in order to obtain a non-finitely tractable sandwich for a structure in the scope of Conjecture 4, it is enough to take a sufficiently large full power thereof, a finite substructure ${𝔖}_1$ whose polymorphisms preserve the inequality, and a finite factor ${𝔖}_2$ by an arbitrary subgroup of automorphisms preserving a linear order and acting with finitely many orbits.

In the context of infinite-domain CSPs, the influence of topological properties of the polymorphism clones of $\omega$-categorical structures has received much attention, with various results claiming their relevance [26] or irrelevance [11]: while generally, whether or not an $\omega$-categorical structure $𝔄$ pp-constructs ${𝔎}_3$ (or pp-interprets another $\omega$-categorical structure ${𝔄}^{\prime }$) does depend on such topological properties [9, 29, 47, 31], in many situations it does not (see, e.g., [42]). By moving from any $\omega$-categorical model-complete core template to one without algebraicity, Theorem 6 allows us to restrict Conjecture 4 to a class of topologically well-behaved structures. Namely, for those recent research suggests that often the algebraic structure determines the topological one; at least this is a fact for the endomorphism monoid, where the relevant topology (pointwise convergence) can then be defined from the algebraic structure of the monoid alone [63]. For $\omega$-categorical structures with algebraicity, on the other hand, various examples [43, 17, 63] show that this need not be the case. This also implies that there is no hope of lifting isomorphisms between endomorphism monoids or polymorphism clones of $\omega$-categorical structures to their counterparts constructed in Theorem 6.

In our proof of Theorem 10, we apply Proposition 17 to a structure which we previously “preprocessed” using Theorem 6 (removing algebraicity) and generic superpositions. It is natural to ask how strong Proposition 17 is on its own: can a result similar to Theorem 10 be proved directly using this proposition, perhaps under a more general structural assumption, e.g. that $𝔄$ is a model-complete core? Here the answer seems to be negative. Consider the model-complete core structure within the scope of Conjecture 4 (${𝔄}_2$ in Example 15); its CSP is polynomial-time tractable [22]. Let $𝔖$ be any finite structure for which there exists a homomorphism $h:𝔖\to {𝔄}^{[d]}$, and let $𝔅$ be an arbitrary $\omega$-categorical expansion of $𝔄$. Let $A_S$ be the set of the elements in $A$ that appear as an entry of some element of $h(S)$, and let ${𝔄}_S$ be the substructure of $𝔄$ on $A_S$. Since ${𝔄}^{[d]}\to {𝔄}_{{}_{/\mathrm{Aut}(𝔅)}}^{[d]}$, the structure ${𝔄}_S^{[d]}$ is a finite cheese for $\mathrm{PCSP}(𝔖,{𝔄}_{{}_{/\mathrm{Aut}(𝔅)}}^{[d]})$.

We claim that $\mathrm{CSP}({𝔄}_S^{[d]})$ is tractable, and hence this PCSP is finitely tractable. To see this, observe that the binary minimum operation $\min (x,y)$ is a polymorphism of $𝔄$. This operation is conservative: $\min (x,y)\subseteq \{x,y\}$ holds for all $x,y$. Hence, its restriction to $A_S^2$ induces a polymorphism of ${𝔄}_S$, which itself induces a polymorphism of ${𝔄}_S^{[d]}$ through its component-wise action. Since this operation is cyclic, ${𝔄}_S^{[d]}$ does not pp-construct ${𝔎}_3$ [9, Theorem 1.4], and hence we are done by Theorem 1. This issue cannot be fixed simply by taking an expansion of $𝔄$ by the inequality relation $\ne$ because $\mathrm{CSP}(𝔄;\ne )$ is NP-complete [22].