The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom

Every finite integral representable relation algebra $\mathbf{A}$ with a flexible atom has a normal representation $\mathfrak{B}$; for completeness, and since we are not aware of a reference for this fact, we include a proof in Section 3. It follows that the classification question about the complexity of the network satisfaction problem of $\mathbf{A}$ can be translated into a question about the complexity of the constraint satisfaction problem for the relational structure $\mathfrak{B}$.

We then associate a finite relational structure $\mathfrak{O}$ to $\mathfrak{B}$ and show that $\operatorname{CSP}(\mathfrak{B})$ can be reduced to $\operatorname{CSP}(\mathfrak{O})$ in polynomial-time (Section 4). If the structure $\mathfrak{O}$ satisfies the condition of the first case in Theorem 1.1, then known results about finite-domain $\operatorname{CSP}$s imply that $\operatorname{CSP}(\mathfrak{O})$ is in P [Bul03, Bul16, Bar11], and hence $\operatorname{CSP}(\mathfrak{B})$ is in P, too. If the first case in Theorem 1.1 does not apply, then known results about finite-domain algebras imply that there are $a,b\in A_{0}$ such that the canonical polymorphisms of $\mathfrak{B}$ act as a projection on $\{a,b\}$ [Bul03, Bul16, Bar11]. We first observe NP-hardness of $\operatorname{CSP}(\mathfrak{B})$ if $\mathfrak{B}$ does not have a binary injective polymorphism (Section 6). If $\mathfrak{B}$ has a binary injective polymorphism, we use results from structural Ramsey theory to show that $\mathfrak{B}$ must even have a binary injective polymorphism which is canonical (Section 7). This implies that none of $a,b$ equals $\operatorname{Id}\in A$. We then prove that ${\mathfrak{B}}$ does not have a binary $\{a,b\}$-symmetric polymorphism; also in this step, we apply Ramsey theory. In Section 8 we show that this in turn implies that all polymorphisms of ${\mathfrak{B}}$ must be canonical on $\{a,b\}$. Finally, we show that ${\mathfrak{B}}$ cannot have a polymorphism which acts as a majority or as a minority on $\{a,b\}$, and thus by Schaefer’s theorem all polymorphisms of ${\mathfrak{B}}$ act as a projection on $\{a,b\}$. This is again implied by results from Section 7. Finally it follows that $\operatorname{CSP}(\mathfrak{B})$ is NP-hard. This concludes the proof of Theorem 1.1.

Our proof follows a strategy that was applied several times in the study of infinite-domain constraint satisfaction problems and recently described and generalized by [MP20]. We give some details about this in Section 10.

Section 2 introduces all the basic concepts and tools that are used in this article. In Section 3 we define flexible atoms and obtain first results about representable relation algebras with a flexible atom. Section 4 is dedicated to the atom structure and the polynomial-time tractability results. In Section 5 we provide an additional perspective on the class of computational problems under consideration; in this section we define those problems completely without the use of the relation algebra framework. The reader can get better intuition of the class of problems studied in this article, however our results and proofs do not rely on that section. The Sections 6-8 contain the main parts of the proof as outlined in the previous paragraph. In Section 9 we put everything together and prove the main theorem. We end with a conclusion and a small discussion of our result.

Let $\mathbb{N}$ denote the natural numbers starting with $0$ and define $\mathbb{N}_{+}:=\mathbb{N}\setminus\{0\}$. A signature $\tau$ is a set of relation symbols and function symbols. Each symbol is associated with a natural number, called the arity of the symbol. Function symbols of arity $0$ are called constant symbols. A $\tau$-structure is a tuple $\mathfrak{A}=(A;(Q^{\mathfrak{A}})_{Q\in\tau})$ where $A$ is a set, called the domain of $\mathfrak{A}$, such that for every $Q\in\tau$:

• $\bullet$

  if $Q$ is a relation symbol of arity $n\in\mathbb{N}$, then $Q^{\mathfrak{A}}$ is a subset of $A^{n}$,

• $\bullet$

  if $Q$ is a function symbol of arity $n\in\mathbb{N}$, then $Q^{\mathfrak{A}}$ is an operation $A^{n}\rightarrow A$.

Note that by $A^{0}=\{\emptyset\}$ a subset of $A^{0}$ can be seen as a Boolean value and the operation $f\colon A^{0}\rightarrow A$ can be interpreted as a constant. As long as there is no risk of confusion we will often use the function symbols for the corresponding functions, and the relation symbols for the corresponding relations, i.e., we use $Q$ instead of $Q^{\mathfrak{A}}$.

Let $\mathfrak{A}$ and $\mathfrak{B}$ be two $\tau$-structures. A homomorphism h from $\mathfrak{A}$ to $\mathfrak{B}$ is a function $h\colon A\rightarrow B$ such that

• $\bullet$

  for every relation symbol $Q$ of arity $n\in\mathbb{N}$ and every tuple $(a_{1},\ldots,a_{n})\in A^{n}$, we have that $(a_{1},\ldots,a_{n})\in Q^{\mathfrak{A}}\Rightarrow(h(a_{1}),\ldots,h(a_{n}))\in Q^{\mathfrak{B}}$;

• $\bullet$

  for every function symbol $Q$ of arity $n\in\mathbb{N}$ and every tuple $(a_{1},\ldots,a_{n})\in A^{n}$, we have that $h(Q^{\mathfrak{A}}(a_{1},\ldots,a_{n}))=Q^{\mathfrak{B}}(h(a_{1}),\ldots,h(a_{n}))$.

In the case that $\tau$ contains only function symbols and $h$ is surjective, then $\operatorname{\mathfrak{B}}$ is called homomorphic image of $\operatorname{\mathfrak{A}}$. In general, the homomorphism $h$ is called an embedding if $h$ is injective and satisfies

• $\bullet$

  for every relation symbol $Q$ of arity $n\in\mathbb{N}$ and every tuple $(a_{1},\ldots,a_{n})\in A^{n}$, we have that $(a_{1},\ldots,a_{n})\in Q^{\mathfrak{A}}\Leftrightarrow(h(a_{1}),\ldots,h(a_{n}))\in Q^{\mathfrak{B}}$.

A surjective embedding is called an isomorphism. An endomorphism of a $\tau$-structure $\operatorname{\mathfrak{A}}$ is a homomorphism from $\operatorname{\mathfrak{A}}$ to $\operatorname{\mathfrak{A}}$ and an automorphism of $\operatorname{\mathfrak{A}}$ is an isomorphism from $\operatorname{\mathfrak{A}}$ to $\operatorname{\mathfrak{A}}$. We denote by $\operatorname{Aut}(\mathfrak{A})$ the group of all automorphisms of $\operatorname{\mathfrak{A}}$.

A $\tau$-structure $\operatorname{\mathfrak{A}}$ is a substructure of a $\tau$-structure $\operatorname{\mathfrak{B}}$ if

• $\bullet$

  $A\subseteq B$;

• $\bullet$

  for every relation symbol $Q$ of arity $n\in\mathbb{N}$ and every tuple $(a_{1},\ldots,a_{n})\in A^{n}$, we have that $(a_{1},\ldots,a_{n})\in Q^{\mathfrak{A}}$ if and only if $(a_{1},\ldots,a_{n})\in Q^{\mathfrak{B}}$;

• $\bullet$

  for every function symbol $Q$ of arity $n\in\mathbb{N}$ and every tuple $(a_{1},\ldots,a_{n})\in A^{n}$, we have that $Q^{\mathfrak{A}}(a_{1},\ldots,a_{n})=Q^{\mathfrak{B}}(a_{1},\ldots,a_{n})$.

Note that for every subset $A^{\prime}\subseteq B$ of the domain of a $\tau$-structure $\operatorname{\mathfrak{B}}$ there exists a unique substructure $\operatorname{\mathfrak{A}}$ of $\operatorname{\mathfrak{B}}$ with smallest domain $A$ and $A^{\prime}\subseteq A$. We call this the substructure of $\operatorname{\mathfrak{B}}$ induced by $A$.

Let $\operatorname{\mathfrak{A}}$ and $\operatorname{\mathfrak{B}}$ be $\tau$ structures. The direct product $\operatorname{\mathfrak{C}}=\operatorname{\mathfrak{A}}\times\operatorname{\mathfrak{B}}$ is the $\tau$-structure where

• $\bullet$

  $A\times B$ is the domain of $\operatorname{\mathfrak{C}}$;

• $\bullet$

  for every relation symbol $Q$ of arity $n\in\mathbb{N}$ and every tuple $((a_{1},b_{1}),\ldots,(a_{n},b_{n}))\in(A\times B)^{n}$, we have that $((a_{1},b_{1}),\ldots,(a_{n},b_{n}))\in Q^{\mathfrak{C}}$ if and only if $(a_{1},\ldots,a_{n})\in Q^{\mathfrak{A}}$ and $(b_{1},\ldots,b_{n})\in Q^{\mathfrak{B}}$;

• $\bullet$

  for every function symbol $Q$ of arity $n\in\mathbb{N}$ and every tuple $((a_{1},b_{1}),\ldots,(a_{n},b_{n}))\in(A\times B)^{n}$, we have that $Q^{\mathfrak{C}}((a_{1},b_{1}),\ldots,(a_{n},b_{n}))=(Q^{\mathfrak{A}}(a_{1},\ldots,a_{n}),Q^{\mathfrak{B}}(b_{1},\ldots,b_{n}))$.

We denote the direct product $\operatorname{\mathfrak{A}}\times\operatorname{\mathfrak{A}}$ by $\operatorname{\mathfrak{A}}^{2}$. The $k$-fold product $\operatorname{\mathfrak{A}}\times\cdots\times\operatorname{\mathfrak{A}}$ is defined analogously and denoted by $\operatorname{\mathfrak{A}}^{k}$.

Structures with a signature that only contains function symbols are called algebras and structure with purely relational signature are called relational structures. Since we do not deal with signatures of mixed type in this article, we will from now on use the term structure for relational structures only.

Relation algebras that are not representable have a trivial network satisfaction problem, namely the class of yes-instances of their network satisfaction problem is empty (see Definition 2.5). We thus omit the definition of relation algebras and start immediately with the simpler definition of representable relation algebras; here we basically follow the textbook by [Mad06b].

The class of representable relation algebras, denoted by $\operatorname{RRA}$, consists of all algebras with signature $\tau=\{~{}\cup,~{}\bar{}~{},~{}0,~{}1,~{}\operatorname{Id},~{}^{\smile},~{}\circ\}$ with corresponding arities $2,1,0,0,0,1$ and $2$ that are isomorphic to some proper relation algebra. We use bold letters (such as $\bf A$) to denote algebras from $\operatorname{RRA}$ and the corresponding roman letter (such as $A$) to denote the domain of the algebra. An algebra is called finite if its domain is finite. We call $\mathbf{A}\in\operatorname{RRA}$ symmetric if all its elements are symmetric, i.e., $a^{\smile}=a$ for every $a\in A$.

According to the previous definition, an algebra $\mathbf{A}$ is in $\operatorname{RRA}$ if it has an isomorphism to a proper relation algebra. Such an isomorphism is usually called the representation of $\bf A$. To link the theory of relation algebras with model theory it will be convenient to view representations of algebras in $\operatorname{RRA}$ as relational structures and to not use the classical notation here. However, it is easy to see that the existence of a representation is equivalent under both definitions.

Let $\mathbf{A}=(A;~{}\cup,~{}\bar{}~{},~{}0,~{}1,~{}\operatorname{Id},~{}^{\smile},~{}\circ)$ be a representable relation algebra and let us define a new operation $x\cap y:=\overline{\overline{x}\cup\overline{y}}$ on the set $A$. Then the algebra $(A;~{}\cup,~{}\cap,~{}\bar{}~{},~{}0,~{}1)$ is by definition a Boolean algebra and induces therefore a partial order $\leq$ on $A$, which is defined by $x\leq y:\Leftrightarrow x\cup y=y$. Note that for proper relation algebras, this ordering coincides with the set-inclusion order. The minimal elements of this order in $A\setminus\{0\}$ are called atoms. The set of atoms of $\bf A$ is denoted by $A_{0}$. A tuple $(x,y,z)\in(A_{0})^{3}$ is called an allowed triple if $z\leq x\circ y$. Otherwise, $(x,y,z)$ is called a forbidden triple and in this case $\overline{z}\cup\overline{x\circ y}=1$. We say that a relational $A$-structure $\mathfrak{B}$ induces a forbidden triple (from $\mathbf{A}$) if there exists $b_{1},b_{2},b_{3}\in B$ and $(x,y,z)\in(A_{0})^{3}$ such that $x(b_{1},b_{2}),y(b_{2},b_{3})$ and $z(b_{1},b_{3})$ hold and $(x,y,z)$ is a forbidden triple. Note that a representation of $\bf A$ does not induce a forbidden triple.

We give an example of an instance of the $\operatorname{NSP}$ for a representable relation algebra. The numbering of the representable relation algebra is by [AM94].

We will in the following assume that for an $\mathbf{A}$-network $(V;f)$ it holds that $f(V^{2})\subseteq A\setminus\{0\}$. Otherwise, $(V;f)$ is not satisfiable. Note that every $\mathbf{A}$-network $(V;f)$ can be viewed as an $A$-structure $\mathfrak{C}$ on the domain $V$: for all $x,y\in V$ and $a\in A$ the relation $a^{\mathfrak{C}}(x,y)$ holds if and only if $f(x,y)=a$.

In this section we consider a subclass of $\operatorname{RRA}$ introduced by Hirsch in 1996. For representable relation algebras $\bf A$ from this class, $\operatorname{NSP}(\bf A)$ corresponds naturally to a constraint satisfaction problem (CSP). In the last two decades a rich and fruitful theory emerged to analyse the computational complexity of CSPs. We use this theory to obtain results about the computational complexity of NSPs.

In the following let $\mathbf{A}$ be in $\operatorname{RRA}$. An $\mathbf{A}$-network $(V;f)$ is called closed (transitively closed in the work by [Hir97]) if it is total and for all $x,y,z\in V$ it holds that $f(x,x)\leq\operatorname{Id}$, $f(x,y)=f(y,x)^{\smile}$, and $f(x,z)\leq f(x,y)\circ f(y,z)$. It is called atomic if the range of $f$ only contains atoms from $\mathbf{A}$.

As usual, formulas without free variables are called sentences. A relational structure is called connected if it is not the disjoint union of two structures. A connected component of a relational structure $\mathfrak{C}$ is a substructure $\mathfrak{B}$ of $\mathfrak{C}$ that is maximal with respect to domain inclusion and is connected. For every primitive positive $\tau$-sentence $\varphi$ with variable set $X$ the canonical database $D(\varphi)$ is defined as the $\tau$-structure on $X$ where $x\in X^{m}$ is in the relation $R^{D(\varphi)}$ for $R\in\tau$ if and only if $R(x)$ is a conjunct from $\varphi$. Conversely every relational $\tau$-structure $\mathfrak{A}$ induces a primitive positive $\tau$-sentence on the variable set $A$, the so-called conjunctive query, simply by taking the conjunction all atomic formulas that hold in $\mathfrak{A}$. We say that the primitve positive $\tau$-sentences $\varphi_{1},\ldots,\varphi_{n}$ are the connected components of a primitive positive $\tau$-sentence $\varphi$ if they are the conjunctive queries of the connected components of the canonical database $D(\varphi)$.

Consider the following translation which associates to each $\mathbf{A}$-network $(V;f)$ a primitive positive $A$-sentences $\varphi$ as follows: the variables of $\varphi$ are the elements of $V$ and $\varphi$ contains for every $(x,y)$ in the domain of $f$ the conjunct $a(x,y)$ if and only if $f(x,y)=a$ holds. For the other direction let $\varphi$ be an $A$-sentence with variable set $X$ and consider the $\mathbf{A}$-network $(X;f)$ with the following definition: for every $x,y\in X$, if $(x,y)$ does not appear in any conjunct from $\varphi$ we leave $f(x,y)$ undefined, otherwise let $a_{1}(x,y),\ldots,a_{n}(x,y)$ all the conjuncts from $\varphi$ that contain $(x,y)$. We compute in $\mathbf{A}$ the element $a:=a_{1}\cap\ldots\cap a_{n}$ and define $f(x,y):=a$.

The following theorem, which subsumes the connection between network satisfaction problems and constraint satisfaction problems is based on this natural 1-to-1 correspondence between $\mathbf{A}$-networks and $A$-sentences.

Let $\tau$ be a finite relational signature. The class of finite $\tau$-structures that embed into a $\tau$-structure $\mathfrak{B}$ is called the age of $\mathfrak{B}$, denoted by $\operatorname{Age}(\mathfrak{B})$. If $\mathcal{F}$ is a class of finite $\tau$-structures, then $\textup{Forb}(\mathcal{F})$ is the class of all finite $\tau$-structures $\mathfrak{A}$ such that no structure from $\mathcal{F}$ embeds into $\mathfrak{A}$. A class $\mathcal{C}$ of finite $\tau$ structures is called finitely bounded if there exists a finite set of finite $\tau$-structures $\mathcal{F}$ such that ${\mathcal{C}}=\textup{Forb}(\mathcal{F})$ (see, e.g., [Mac11]). The structures from $\mathcal{F}$ are called bounds or forbidden substructures. It is easy to see that a class $\mathcal{C}$ of $\tau$-structures is finitely bounded if and only if it is axiomatisable by a universal $\tau$-sentence. A structure $\mathfrak{B}$ is called finitely bounded if $\operatorname{Age}(\mathfrak{B})$ is finitely bounded.

Let $\mathfrak{B}_{1},\mathfrak{B}_{2}$ be $\tau$-structures. Then $\mathfrak{B}_{1}\cup\mathfrak{B}_{2}$ is the $\tau$-structure on the domain $B_{1}\cup B_{2}$ such that $R^{\mathfrak{B}_{1}\cup\mathfrak{B}_{2}}:=R^{\mathfrak{B}}_{1}\cup R^{\mathfrak{B}}_{2}$ for every $R\in\tau$. If Definition 2.11 holds with $\mathfrak{C}:=\mathfrak{B}_{1}\cup\mathfrak{B}_{2}$ then we say that $\mathcal{C}$ has the free amalgamation property; note that the free amalgamation property implies the strong amalgamation property.

For a structure $\mathfrak{B}$ the automophism group $\operatorname{Aut}(\mathfrak{B})$ is called transitive if $\operatorname{Aut}(\mathfrak{B})$ has only one orbit. We want to remark that if $\mathfrak{B}$ is a normal representation of a finite $\mathbf{A}\in\operatorname{RRA}$ then the 2-orbits of $\operatorname{Aut}(\mathfrak{B})$ are exactly the relations induced by the atoms $A_{0}$ of $\mathbf{A}$.

In this section we present basic notions for the so-called universal-algebraic approach to the study of $\operatorname{CSP}$s.

An operation $f\colon B^{n}\to B$ is called conservative if for all $x_{1},\ldots,x_{n}\in B$ it holds that $f(x_{1},\ldots,x_{n})\in\{x_{1},\ldots,x_{n}\}.$ A clone is called conservative if all its operations are conservative. Note that an operation clone $\mathscr{C}$ on $B$ can be considered as an algebra with domain $B$ and an infinite signature that consists of symbols for all operations in $\mathscr{C}$ (cf. Section 2.1). In this sense a conservative operation clone $\mathscr{C}$ on $B$ induces on every set $A\subseteq B$ a subalgebra. It is easy to see that this subalgebra corresponds to an operation clone on $A$. We call this the restriction of $\mathscr{C}$ to $A$. We later need the following classical result for clones over a two-element set.

Operation clones occur naturally as polymorphism clones of relational structures. If $x_{1},\dots,x_{n}\in B^{k}$ and $f\colon B^{n}\to B$, then we write $f(x_{1},\ldots,x_{n})$ for the $k$-tuple obtained by applying $f$ component-wise to the tuples $x_{1},\ldots,x_{n}$.

In order to provide an additional view on polymorphisms we give the following definition.

It is easy to see that the $n$-ary polymorphisms of $\mathfrak{B}$ are precicely the homomorphisms from $\mathfrak{B}^{n}$ to $\mathfrak{B}$.

The set of all polymorphisms (of all arities) of a relational structure $\mathfrak{B}$ is an operation clone on $B$, which is denoted by $\operatorname{Pol}(\mathfrak{B})$. A Siggers operation is an operation that satisfies the Siggers identity (see Theorem 1.1). The following result can be obtained by combining known results from the literature.

We now discuss fundamental results about the universal-algebraic approach for constraint satisfaction problems of structures with an infinite domain.

The following definition is a preparation to formulate the next theorem which is a well-known condition that implies NP-hardness of $\operatorname{CSP}(\mathfrak{B})$ for homogeneous structures with a finite relational signature.

An operation clone $\mathscr{C}$ on a set $B$ can also be seen as an algebra $\bf B$ with domain $B$ whose signature consists of the operations of $\mathscr{C}$ such that $f^{\bf B}:=f$ for all $f\in{\mathscr{C}}$.

The following is a classical condition for NP-Hardness, see for example Theorem 10 in the survey by [Bod08].

In the following let $\bf A\in\operatorname{RRA}$ be finite and with normal representation $\mathfrak{B}$.

An operation $f\colon B^{n}\rightarrow B$ is called edge-conservative if it satisfies for all $x,y\in B^{n}$ and all $a_{1},\ldots,a_{n}\in A_{0}$

Note that for every $D\subseteq A_{0}$ the structure $\mathfrak{B}$ contains the relation $\bigcup_{a_{i}\in D}a_{i}^{\mathfrak{B}}$. Therefore the next proposition follows immediately since polymorphisms of $\mathfrak{B}$ preserve all relations of $\mathfrak{B}$.

We denote by $\operatorname{Pol^{can}}(\mathfrak{B})$ the set of all polymorphisms of $\mathfrak{B}$ that are canonical with respect to $\mathfrak{B}$. It will always be clear from the context what the domain of a behaviour $\bar{f}$ is. An operation $f\colon S^{2}\to S$ is called symmetric if for all $x,y\in S$ it holds that $f(x,y)=f(y,x)$. An $X$-canonical function $f$ is called $X$-symmetric if the behaviour of $f$ on $X$ is symmetric.

We avoid giving an introduction to Ramsey theory, since the only usage of the Ramsey property is via Theorem 2.26, and rather refer to the survey by [Bod15] for an introduction.

Let $\mathfrak{A}$ be a homogeneous $\tau$-structure such that $\operatorname{Age}({\mathfrak{A}})$ has the strong amalgamation property. Then the class of all $(\tau\cup\{<\})$-structures $\mathfrak{A}$ such that $<^{\mathfrak{A}}$ is a linear order and whose $\tau$-reduct (i.e. the structure on the same domain, but only with the relations that are denoted by symbols from $\tau$, see e.g. the book by [Hod97]) is from $\operatorname{Age}({\mathfrak{A}})$ is a strong amalgamation class, too (see e.g. [Bod15]). By Theorem 2.12 there exists an up to isomorphism unique countable homogeneous structure of that age, which we denote by $\mathfrak{A}_{<}$. It can be shown by a straightforward back-and-forth argument that $\mathfrak{A}_{<}$ is isomorphic to an expansion of $\mathfrak{A}$, so we identify the domain of $\mathfrak{A}$ and of $\mathfrak{A}_{<}$ along this isomorphism, and call $\mathfrak{A}_{<}$ the expansion of $\mathfrak{A}$ by a generic linear order.

The following theorem gives a connection of the Ramsey property with the existence of canonical functions and plays a key role in our analysis.

Let $\mathbf{A}\in\operatorname{RRA}$ and let $I:=\{a\in A\mid a\leq\operatorname{Id}\}$. The atoms in $I\cap A_{0}$ are called identity atoms. Therefore, $\mathbf{A}$ is integral if and only if $\mathbf{A}$ has exactly one identity atom. The first claim of the following lemma is a well-known fact about atoms of representable relation algebras. This fact is used to prove a second claim about representable relation algebras with a flexible atom. In simple terms, this claim states that a representation of a non-integral representable relation algebra with a flexible atom is only “square” on precisely those elements that are in one certain identity atom.