The algebraic structure of the densification and the sparsification tasks for CSPs

Abstract

The tractability of certain CSPs for dense or sparse instances is known from the 90s. Recently, the densification and the sparsification of CSPs were formulated as computational tasks and the systematical study of their computational complexity was initiated. We approach this problem by introducing the densification operator, i.e. the closure operator that, given an instance of a CSP, outputs all constraints that are satisfied by all of its solutions. According to the Galois theory of closure operators, any such operator is related to a certain implicational system (or, a functional dependency) Σ. We are specifically interested in those classes of fixed-template CSPs, parameterized by constraint languages Γ, for which there is an implicational system Σ whose size is a polynomial in the number of variables n. We show that in the Boolean case, such implicational systems exist if and only if Γ is of bounded width. For such languages, Σ can be computed in log-space or in a logarithmic time with a polynomial number of processors. Given an implicational system Σ, the densification task is equivalent to the computation of the closure of input constraints. The sparsification task is equivalent to the computation of the minimal key.

1 Introduction

In the constraint satisfaction problem (CSP) [1,2,3] we are given a set of variables with prescribed domains and a set of constraints. The task’s goal is to assign each variable a value such that all the constraints are satisfied. Given an instance of CSP, besides the classical formulation, one can formulate many other tasks, such as maximum/minimum CSPs (Max/Min-CSPs) [4], valued CSP (VCSPs) [5, 6], counting CSPs [7, 8], promise CSPs [9, 10], quantified CSPs [11,12,13], and others. Thus, the computational task of finding a single solution is not the only aspect that is of interest from the perspective of applications of CSPs.

Sometimes in applications we have a CSP instance that defines a set of solutions, and we need to preprocess the instance by making it denser (i.e. adding new constraints) or, vice versa, sparser (removing as many constraints as we can) without changing the set of solutions. Let us give an example of such an application. The paper by Jia Deng et al. [14] is dedicated to the Conditional Random Field (CRF) based on the so-called HEX graphs. The algorithm for the inference in CRFs presented there is based on the standard junction tree algorithm [15], but with one additional trick — before constructing the junction tree of the factor graph, the factor tree is sparsified. This step aims to make the factor graph as close to the tree structure as possible. After that step, cliques of the junction tree are expected to have fewer nodes. The sparsification of the HEX graph done in this approach is equivalent to the sparsification of a CSP instance, i.e. the deletion of as many constraints as possible while maintaining the set of solutions. The term “sparsification” is also used in a related line of work in which the goal is, given a CSP instance, to reduce the number of constraints without changing the satisfiability of an instance [16, 17].

As was suggested in [14], the densification of a CSP instance could also help make inference algorithms more efficient. If the factor tree is densified, then for every clique c of the factor graph, the number of consistent assignments to variables of the clique c is smaller. Thus, reducing the state space for each clique makes the inference faster. The sparsification-densification approach substantially accelerates the computation of the marginals as the number of nodes grows.

It is well-known that the complexity of the sparsification problem, as well as the worst-case sparsifiability, depends on the constraint language, i.e. the types of constraints allowed in CSP. The computational complexity was completely classified for constraint languages consisting of the so-called irreducible relations [18].

For a constraint language that consists of Boolean relations of the form A₁ ∧ A₂ ∧ ... ∧ A_n → B (so-called pure Horn clauses), the sparsification task is equivalent to the problem of finding a minimum size cover of a given functional dependency (FD) table. The last problem was studied in database theory long ago and is considered a classical topic. It was shown that this problem is NP-hard both in the general case and in the case a cover is restricted to be a subset of the given FD table. Surprisingly, if we re-define the size of a cover as the number of distinct left-hand side expressions A₁ ∧ A₂ ∧ ... ∧ A_n, then the problem is polynomially solvable [19].

An important generalization of the previous constraint language is a set of Horn clauses (i.e. B can be equal to False). The sparsification problem for this language is known by the name Horn minimization, i.e. it is a problem of finding the minimum size Horn formula that is equivalent to an input Horn formula. Horn minimization is NP-hard if the number of clauses is to be minimized [20, 21], or if the number of literals is to be minimized [22]. Moreover, in the former case Horn minimization cannot be $2^{\log ^{1-\epsilon } (n)}$-approximated if $\text {NP}\not \subseteq \text {DTIME}(n^{\text {polylog}(n)})$ [23].

An example of a tractable sparsification problem is 2-SAT formula minimization [24] which corresponds to the constraint language of binary relations over the Boolean domain.

The key idea of this paper’s approach is to consider both densification and sparsification as two operations defined on the same set, i.e. the set of possible constraints. We observe that the densification is a closure operator on a finite set, and therefore, according to Galois theory [25], it can be defined using a functional dependency table, or so-called implicational system Σ (over a set of possible constraints and, maybe, some additional literals). It turns out that Σ can have a size bounded by some polynomial of the number of variables only if the constraint language is of bounded width (for tractable languages not of bounded width, the size of Σ could still be substantially smaller than for NP-hard languages). For the Boolean domain, all languages of bounded width have a polynomial-size implicational system Σ.

Given an implicational system Σ, the sparsification problem can be reformulated as a problem of finding the minimal key in Σ, i.e. such a set of constraints whose densification is the same as the densification of initial constraints. This task was actively studied in database theory, and we exploit the standard algorithm for the solution of the minimal key problem, found by Luchessi and Osborn [26]. If $|{\Sigma }| = {\mathcal O}(\text {poly}(n))$ and literals of Σ are all from the set of possible constraints, this leads us to a ${\mathcal O}(\text {poly}(n)\cdot N^{2})$-sparsification algorithm where N is the number of non-redundant sparsifications of an input instance. This algorithm can be applied to the Horn minimization problem, and, to our knowledge, this is the first algorithm that is polynomial in N. Of course, in the worst-case N is large.

Besides the mentioned works, densification/sparsification tasks were also studied for soft CSPs, and this unrelated research direction includes graph densification [27,28,29], binary CSP sparsification [30,31,32,33,34] and spectral sparsification of graphs and hypergraphs [35, 36]. In the 90’s it was found that dense CSP instances (i.e. when the number of k-ary constraints is Θ(n^k)) admit efficient algorithms for the Max-k-CSP and the maximum assignment problems [37,38,39]. Though we deal with crisp CSPs and not any CSP instance can be densified to Θ(n^k) constraints, the idea to densify a CSP instance seems natural in this context. Note that the densification of a CSP that we study in our paper is substantially different from the notion of the densification of a graph. Initially, Hardt et al. [27] define the densification of the graph G = (V,E) as a new graph $H=(V, E^{\prime }), E^{\prime }\supseteq E$ such that the cardinalities of cuts in G and H are proportional. In [28, 29] and in the Ph.D. Thesis [40] the densification was naturally applied in a clustering problem to neighborhood graphs to make more intra-class links and smaller overhead of inter-class links. It was shown that this makes the Laplacian of a graph better conditioned for a subsequent application of spectral methods. A theoretical analysis of the densification/sparsification tasks for soft CSPs requires mathematical tools substantially different from those that we develop in the paper.

2 Preliminaries

We assume that P≠NP. The set {1,...,k} is denoted by [k]. Given a relation ${\varrho }\subseteq R^{s}$ and a tuple $\mathbf {a}\in R^{s^{\prime }}$, by ∥ϱ∥ and |a| we denote s and $s^{\prime }$, respectively. A relational structure is a tuple R = (R,r₁,...,r_k) where R is finite set, called the domain of R, and $r_{i}\subseteq R^{\|r_{i}\|}$, i ∈ [k]. If p₀ ∈ [∥ϱ∥], then $\text {pr}_{\{p_{0}\}} ({\varrho }) = \{a_{p_{0}}| (a_{1}, ..., a_{k})\in {\varrho }\}$, if p₀ < p₁ ≤∥ϱ∥, then $\text {pr}_{\{p_{0},p_{1}\}} ({\varrho }) = \{(a_{p_{0}}, a_{p_{1}})| (a_{1}, ..., a_{k})\in {\varrho }\}$ etc.

2.1 The homomorphism formulation of CSP

Let us define first the notion of a homomorphism between relational structures.

Definition 1

Let R = (V,r₁,...,r_s) and $\mathbf {R}^{\prime } = (V^{\prime }, r^{\prime }_{1}, ..., r^{\prime }_{s})$ be relational structures with a common signature (that is arities of r_i and $r^{\prime }_{i}$ are the same for every i ∈ [s]). A mapping $h\colon V \to V^{\prime }$ is called a homomorphism from R to $\mathbf {R}^{\prime }$ if for every i ∈ [s] and for any $(x_{1}, ..., x_{\|{r_{i}}\|}) \in r_{i}$ we have that $\big ((h(x_{1}), ..., h(x_{\|{r^{\prime }_{i}}\|})\big ) \in r^{\prime }_{i}$. The set of all homomorphisms from R to $\mathbf {R}^{\prime }$ is denoted by $\text {Hom}(\mathbf {R}, \mathbf {R}^{\prime })$.

The classical CSP can be formulated as a homomorphism problem.

Definition 2

The CSP is a search task with:

• An instance: two relational structures with a common signature, R = (V,r₁,...,r_s) and Γ = (D,ϱ₁,...,ϱ_s).

• An output: a homomorphism h : R →Γ if it exists, or answer None, if it does not exist.

A finite relational structure Γ = (D,ϱ₁,...,ϱ_s) over a fixed finite domain D is sometimes called a template. For such Γ we will denote by Γ (without boldface) the set of relations {ϱ₁,...,ϱ_s}. The set Γ is called the constraint language.

Definition 3

The fixed template CSP for a given template Γ = (D,ϱ₁,...,ϱ_s), denoted CSP(Γ), is defined as follows: given a relational structure R = (V,r₁,...,r_s) of the same signature as Γ, solve the CSP for an instance (R,Γ). If CSP(Γ) is solvable in a polynomial time, then Γ is called tractable. Otherwise, Γ is called NP-hard [2, 3].

2.2 Algebraic approach to CSPs

In the paper we will need standard definitions of primitive positive formulas and polymorphisms.

Definition 4

Let τ = {π₁,...,π_s} be a set of symbols for predicates, with the arity n_i assigned to π_i. A first-order formula Φ(x₁,...,x_k) = ∃x_k+ 1...x_nΞ(x₁,...,x_n) where ${\Xi }(x_{1}, ..., x_{n}) = \bigwedge _{t=1}^{N} \pi _{j_{t}} (x_{o_{t1}}, x_{o_{t2}}, ..., x_{o_{tn_{j_{t}}}})$, j_t ∈ [s], o_tq ∈ [n] is called the primitive positive formula over the vocabulary τ. For a relational structure R = (V,r₁,...,r_s), ∥r_i∥ = n_i,i ∈ [s], Φ^R denotes a k-ary predicate

$$\{(a_{1}, ..., a_{k})|a_{i}\in V, i\in [k], \exists a_{k+1}, \cdots, a_{n}\in V: (a_{o_{t1}}, a_{o_{t2}}, ..., a_{o_{tn_{j_{t}}}})\in r_{j_{t}}, t\in [N]\},$$

i.e. the result of interpreting the formula Φ on the model R, where π_i is interpreted as r_i.

For Γ = (D,ϱ₁,...,ϱ_s) and τ = {π₁,...,π_s}, let us denote the set {Ψ^Γ|Ψ is primitive positive formula over τ} by 〈Γ〉.

Definition 5

Let ${\varrho } \subseteq D^{m}$ and f : Dⁿ → D. We say that the predicate ϱ is preserved by f (or, f is a polymorphism of ϱ) if, for every $\left ({{x_{1}^{i}} ,...,{x_{m}^{i}} } \right ) \in {\varrho }, 1 \leq i \leq n$, we have that $\left ({f\left ({{x_{1}^{1}} ,...,{x_{1}^{n}} } \right ),...,f\left ({{x_{m}^{1}} ,...,{x_{m}^{n}} } \right )} \right ) \in {\varrho }$.

For a set of predicates ${\Gamma }\subseteq \{{\varrho }| {\varrho }\subseteq D^{m}\}$, let $\text {Pol}\left ({\Gamma } \right )$ denote the set of operations $f: D^{n} \rightarrow D$ such that f is a polymorphism of all predicates in Γ. For a set of operations $F\subseteq \{f| f: D^{n}\rightarrow D\}$, let $\text {Inv}\left (F \right )$ denote the set of predicates ${\varrho }\subseteq D^{m}$ preserved under the operations of F. The next result is well-known [41, 42].

Theorem 1 (Geiger, Bodnarchuk, Kaluznin, Kotov, Romov)

For a set of predicates Γ over a finite set D, $\langle {\Gamma } \rangle = \text {Inv}\left (\text {Pol}\left ({\Gamma } \right ) \right )$.

It is well-known that the computational complexity of fixed-template CSPs, counting CSPs, VCSPs etc. is determined by the closure 〈Γ〉, and therefore, by the corresponding functional clone $\text {Pol}\left ({\Gamma } \right )$.

3 The fixed template densification and sparsification problems

Let us give a general definition of maximality and list some properties of maximal instances.

Definition 6

An instance (R,Γ) of CSP, where R = (V,r₁,...,r_s) and Γ = (D,ϱ₁,...,ϱ_s), is said to be maximal if for any $\mathbf {R}^{\prime } = (V,r^{\prime }_{1}, ..., r^{\prime }_{s})$ such that $r^{\prime }_{i}\supseteq r_{i}$, i ∈ [s] we have $\text {Hom}(\mathbf {R}, \boldsymbol {\Gamma }) \ne \text {Hom}(\mathbf {R}^{\prime }, \boldsymbol {\Gamma })$, unless $\mathbf {R}^{\prime } = \mathbf {R}$.

The following characterization of maximal instances is evident from Definition 6 (also, see Theorem 1 in [43]).

Theorem 2

An instance (R = (V,r₁,...,r_s),Γ = (D,ϱ₁,...,ϱ_s)) is maximal if and only if for any i ∈ [s] and any $(v_{1}, ..., v_{\|{r_{i}}\|})\notin r_{i}$ there exists h ∈Hom(R,Γ) such that $(h(v_{1}), ..., h(v_{\|{r_{i}}\|}))\notin {\varrho }_{i}$.

One can prove the following simple existence theorem (Statement 1 in [43]).

Theorem 3

For any instance (R = (V,r₁,...,r_s),Γ = (D,ϱ₁,...,ϱ_s)) of CSP, there exists a unique maximal instance $(\mathbf {R}^{\prime }= (V,r^{\prime }_{1}, ..., r^{\prime }_{s}), \boldsymbol {\Gamma })$ such that $r^{\prime }_{i}\supseteq r_{i}, i\in [s]$ and $\text {Hom}(\mathbf {R}, \boldsymbol {\Gamma }) = \text {Hom}(\mathbf {R}^{\prime }, \boldsymbol {\Gamma })$. Moreover, if Hom(R,Γ)≠∅, then

$$r^{\prime}_{i}=\bigcap_{h\in \text{Hom}(\mathbf{R}, \boldsymbol{\Gamma})} h^{-1}({\varrho}_{i}), i\in [s]$$

Thus, the maximal instance $(\mathbf {R}^{\prime }, \boldsymbol {\Gamma })$ from Theorem 3 can be called the densification of (R,Γ). Let us now formulate constructing $(\mathbf {R}^{\prime }, \boldsymbol {\Gamma })$ from (R,Γ) as an algorithmic problem.

Definition 7

The densification problem, denoted Dense, is a search task with:

• An instance: two relational structures with a common signature, R = (V,r₁,...,r_s) and Γ = (D,ϱ₁,...,ϱ_s).

• An output: a maximal instance $(\mathbf {R}^{\prime }= (V,r^{\prime }_{1}, ..., r^{\prime }_{s}), \boldsymbol {\Gamma })$ such that $r^{\prime }_{i}\supseteq r_{i}, i\in [s]$ and $\text {Hom}(\mathbf {R}, \boldsymbol {\Gamma }) = \text {Hom}(\mathbf {R}^{\prime }, \boldsymbol {\Gamma })$.

Also, let D be a finite set and Γ a relational structure with a domain D. Then, the fixed template densification problem for the template Γ, denoted Dense(Γ), is defined as follows: given a relational structure R = (V,r₁,...,r_s) of the same signature as Γ, solve the densification problem for an instance (R,Γ).

Let Γ = {ϱ₁,⋯ ,ϱ_s}. The language Γ is called constant-preserving if there is a ∈ D such that (a,⋯ ,a) ∈ ϱ_i for any i ∈ [s]. For a pair (R,Γ), where Γ is not a constant-preserving language, the corresponding densification is non-trivial, i.e. $\mathbf {R}^{\prime }\ne (V, V^{\|r_{1}\|}, \cdots , V^{\|r_{s}\|})$, if and only if Hom(R,Γ)≠∅. Therefore, the densification problem for such templates Γ is at least as hard as the decision form of CSP. In other words, if the decision form of CSP(Γ) is NP-hard (which is known to be polynomially equivalent to the search form), then all the more Dense(Γ) is NP-hard.

For a Boolean constraint language Γ, we say that Γ is Schaefer in one of the following cases: 1) x ∨ y ∈Pol(Γ), 2) x ∧ y ∈Pol(Γ), 3) x ⊕ y ⊕ z ∈Pol(Γ), 4) mjy(x,y,z) = (x ∧ y) ∨ (x ∧ y) ∨ (x ∧ z) ∈Pol(Γ). The complexity of Dense(Γ) in the Boolean case can be simply described by the following theorem whose proof uses earlier results of [44] and [45]. For completeness, a detailed proof can be found in Section 11.

Theorem 4

For D = {0,1}, Dense(Γ) is polynomially solvable if and only if Γ is Schaefer.

Let us introduce the sparsification problem.

Definition 8

An instance (R,Γ) of CSP, where R = (V,r₁,...,r_s) and Γ = (D,ϱ₁,...,ϱ_s), is said to be minimal if for any T = (V,t₁,...,t_s) such that $t_{i}\subseteq r_{i}, i\in [s]$ we have Hom(R,Γ)≠Hom(T,Γ), unless T = R.

Let us define:

$$ \begin{array}{llllll} \text{Min} (\mathbf{R}, \boldsymbol{\Gamma}) = \big\{\mathbf{R}^{\prime}=(V,r^{\prime}_{1}, ..., r^{\prime}_{s}) \mid \text{Hom} (\mathbf{R}, \boldsymbol{\Gamma})=\text{Hom} (\mathbf{R}^{\prime}, \boldsymbol{\Gamma}), (\mathbf{R}^{\prime}, \boldsymbol{\Gamma})\text{ is minimal}\big\} \end{array} $$

(1)

Definition 9

The sparsification problem, denoted Sparse, is a search task with:

• An instance: two relational structures with a common signature, R = (V,r₁,...,r_s) and Γ = (D,ϱ₁,...,ϱ_s).

• An output: List of all elements of Min(R,Γ).

Also, let D be a finite set and Γ a relational structure with a domain D. Then, the fixed template sparsification problem for the template Γ, denoted Sparse(Γ), is defined as follows: given a relational structure R = (V,r₁,...,r_s) of the same signature as Γ, solve the sparsification problem for an instance (R,Γ).

Remark 1

In many aplications Min(R,Γ) is of moderate size, though potentially it can depend on |V | exponentially. Also, $\mathbf {R}^{\prime }=(V,r^{\prime }_{1}, ..., r^{\prime }_{s}) \in \text {Min} (\mathbf {R}, \boldsymbol {\Gamma })$ is not necessarily a substructure of R, i.e. it is possible that $r^{\prime }_{i}\not \subseteq r_{i}$. Enforcing $r^{\prime }_{i}\subseteq r_{i}, i\in [s]$ in the definition of Min(R,Γ) is discussed in Remark 2.

4 Densification as the closure operator

Let us introduce a set of all possible constraints over Γ on a set of variables V:

$$ \mathcal{C}^{\boldsymbol{\Gamma}}_{V} = \{\langle (v_{1}, ..., v_{\|{\varrho}_{i}\|}), {\varrho}_{i}\rangle | i\in [s], v_{1}, ..., v_{\|{\varrho}_{i}\|}\in V\} $$

Any instance of CSP(Γ), a relational structure R = (V,r₁,...,r_s), induces the following subset of $\mathcal {C}^{\boldsymbol {\Gamma }}_{V}$:

$$ \mathcal{C}_{\mathbf{R}} = \{\langle (v_{1}, ..., v_{\|{\varrho}_{i}\|}), {\varrho}_{i}\rangle | i\in [s], (v_{1}, ..., v_{\|{\varrho}_{i}\|})\in r_{i}\} $$

Using that notation, the densification can be understood as an operator $\text {Dense}: 2^{\mathcal {C}^{\boldsymbol {\Gamma }}_{V}}\rightarrow 2^{\mathcal {C}^{\boldsymbol {\Gamma }}_{V}}$ such that:

$$ \begin{array}{llllll} \text{Dense} (\mathcal{C}_{\mathbf{R}}) = \big\{\langle (v_{1}, ..., v_{\|{\varrho}_{i}\|}), {\varrho}_{i}\rangle | i\in [s], (v_{1}, ..., v_{\|{\varrho}_{i}\|})\in \bigcap\limits_{h\in \text{Hom}(\mathbf{R}, \boldsymbol{\Gamma})} h^{-1}({\varrho}_{i}) \big\} \end{array} $$

Thus, in the densification process we start from a set of constraints $\mathcal {C}_{\mathbf {R}}$ and simply add possible constraints to $\text {Dense} (\mathcal {C}_{\mathbf {R}})$ while the set of solutions is preserved. Let us also define $\text {Dense} (\mathcal {C}_{\mathbf {R}}) = \mathcal {C}^{\boldsymbol {\Gamma }}_{V}$ if Hom(R,Γ) = ∅. The densification operator satisfies the following conditions:

• $\text {Dense} (\mathcal {C}_{\mathbf {R}})\supseteq \mathcal {C}_{\mathbf {R}}$ (extensive)

• $\text {Dense} (\text {Dense} (\mathcal {C}_{\mathbf {R}}))=\text {Dense} (\mathcal {C}_{\mathbf {R}})$ (idempotent)

• $\mathcal {C}_{\mathbf {R}^{\prime }}\subseteq \mathcal {C}_{\mathbf {R}} \Rightarrow \text {Dense} (\mathcal {C}_{\mathbf {R}^{\prime }})\subseteq \text {Dense} (\mathcal {C}_{\mathbf {R}})$ (isotone)

Operators that satisfy these three conditions play the central role in universal algebra and are called the closure operators. There exists a duality between closure operators $o:2^{S}\rightarrow 2^{S}$ on a finite set S and the so-called implicational systems (or functional dependencies) on S. Let us briefly describe this duality (details can be found in [25]).

Definition 10

Let S be a finite set. An implicational system Σ on S is a binary relation ${\Sigma }\subseteq 2^{S} \times 2^{S}$. If (A,B) ∈Σ, we write $A\rightarrow B$. A full implicational system on S is an implicational system satisfying the three following properties:

• $A\rightarrow B, B\rightarrow C$ imply $A\rightarrow C$

• $A\subseteq B$ imply $B\rightarrow A$

• $A\rightarrow B$ and $C\rightarrow D$ imply $A\cup C \rightarrow B \cup D$.

Any implicational system ${\Sigma }\subseteq 2^{S} \times 2^{S}$ has a minimal superset ${\Sigma }^{\prime }\supseteq {\Sigma }$ that itself is a full implicational system on S. This system is called the closure of Σ and is denoted by Σ^⊳. Let us call Σ₁ a cover of Σ₂ if ${\Sigma }^{\triangleright }_{1}= {\Sigma }^{\triangleright }_{2}$.

Theorem 5 (p. 264 25)

Any implicational system ${\Sigma }\subseteq 2^{S} \times 2^{S}$ defines the closure operator $o:2^{S}\rightarrow 2^{S}$ by $o(A) = \{x\in S| A\rightarrow \{x\} \in {\Sigma }^{\triangleright }\}$. Any closure operator $o:2^{S}\rightarrow 2^{S}$ on a finite set S defines the full implicational system by $\{A\rightarrow B| B\subseteq o(A)\}$.

From Theorem 5 we obtain that the densification operator $\text {Dense}: 2^{\mathcal {C}^{\boldsymbol {\Gamma }}_{V}}\rightarrow 2^{\mathcal {C}^{\boldsymbol {\Gamma }}_{V}}$ also corresponds to some full implicational system ${\Sigma }_{V}^{\boldsymbol {\Gamma }}\subseteq 2^{\mathcal {C}^{\boldsymbol {\Gamma }}_{V}} \times 2^{\mathcal {C}^{\boldsymbol {\Gamma }}_{V}}$. Note that the system ${\Sigma }_{V}^{\boldsymbol {\Gamma }}$ depends only on the set V and the template Γ, but does not depend on relations r_i,i ∈ [s] of the relational structure R.

Note the densification problem described in Definition 7 can be understood as a computation of the monotone function $\text {Dense}:\cup _{n=1}^{\infty } 2^{\mathcal {C}_{[n]}^{\boldsymbol {\Gamma }} } \to \cup _{n=1}^{\infty } 2^{\mathcal {C}_{[n]}^{\boldsymbol {\Gamma }} }$. With a little abuse of terminology, let us define the class mP/poly as a class of monotone functions $M:\bigcup _{i=0}^{\infty }\{0,1\}^{n_{i}}\to \bigcup _{i=0}^{\infty }\{0,1\}^{m_{i}}$ for which $M(\{0,1\}^{n_{i}})\subseteq \{0,1\}^{m_{i}}$ and $M|_{\{0,1\}^{n_{i}}}$ can be computed by a circuit of size poly(n_i) that uses only ∨ and ∧ in gates. Thus, Dense(Γ) ∈mP/poly denotes the fact that the corresponding densification operator is in mP/poly.

5 The polynomial densification operator

Let denote ${\Sigma }_{n}^{\boldsymbol {\Gamma }} = {\Sigma }_{[n]}^{\boldsymbol {\Gamma }}$. The most general languages with a kind of polynomial densification operator can be described as follows.

Definition 11

The template Γ is said to have a weak polynomial densification operator, if for any $n\in {\mathbb N}$ there exists an implicational system Σ on $S\supseteq {\mathcal C}^{\boldsymbol {\Gamma }}_{n}$ of size $|{\Sigma }| = {\mathcal O}(\text {poly}(n))$ that acts on ${\mathcal C}^{\boldsymbol {\Gamma }}_{n}$ as the densification operator, i.e. ${\Sigma }_{n}^{\boldsymbol {\Gamma }} = \{(A\rightarrow B)\in {\Sigma }^{\triangleright }| A,B\subseteq {\mathcal C}^{\boldsymbol {\Gamma }}_{n}\}$.

Using database theory language [46], the last definition describes such languages Γ for which there exists an implicational system of polynomial size whose projection on ${\mathcal C}^{\boldsymbol {\Gamma }}_{n}$ coincides with ${\Sigma }_{n}^{\boldsymbol {\Gamma }}$. Note that in Definition 11, a weak densification operator acts on a wider set than ${\mathcal C}^{\boldsymbol {\Gamma }}_{n}$: an addition of new literals to ${\mathcal C}^{\boldsymbol {\Gamma }}_{n}$, sometimes, allows to substantially simplify a set of implications [47]. Though we are not aware of an example of a language Γ for which any cover ${\Sigma }\subseteq {\Sigma }_{n}^{\boldsymbol {\Gamma }}$ of ${\Sigma }_{n}^{\boldsymbol {\Gamma }}$ is exponential in size, but still Γ has a weak polynomial densification operator.

6 Main results

Recall that bounded width languages are languages for which ¬CSP(Γ) can be recognized by a Datalog program [1]. Concerning the weak polynomial densification, we obtain the following result.

Theorem 6

For the general domain D, if Γ has a weak polynomial densification operator, then Γ is of bounded width. For the Boolean case, D = {0,1}, Γ has a weak polynomial densification operator if and only if Pol(Γ) contains either ∨, or ∧, or mjy(x,y,z).

The first part of the latter theorem is proved in Section 7 and the Boolean case is considered in Section 13. We also prove the following statement for the sparsification problem (Section 9).

Theorem 7

If ${\Sigma }\subseteq {\Sigma }^{\boldsymbol {\Gamma }}_{V}$ is a cover of ${\Sigma }^{\boldsymbol {\Gamma }}_{V}$ that can be computed in time poly(|V |), then given an instance R = (V,r₁,...,r_s) of Sparse(Γ), all elements of Min(R,Γ) can be listed in time ${\mathcal O} (\text {poly}(|V|)\cdot |\text {Min} (\mathbf {R}, \boldsymbol {\Gamma })|^{2})$.

7 Weak polynomial densification implies bounded width

A set of languages with a weak polynomial densification operator turns out to be a subset of a set of languages of bounded width. Below we demonstrate this fact in two steps. First, we prove that from a weak polynomial densification operator one can construct a polynomial-size monotone circuit that computes ¬CSP(Γ). Further, we exploit a well-known result from a theory of fixed-template CSPs connecting the bounded width with such circuits.

Theorem 8

If Γ has a weak polynomial densification operator, then the decision version of ¬CSP(Γ) can be computed by a polynomial-size monotone circuit.

Proof

If Γ is constant-preserving, then ¬CSP(Γ) is trivial, i.e. we can assume that Γ is not constant-preserving. Let Σ_n be an implicational system on $S_{n}\supseteq {\mathcal C}^{\boldsymbol {\Gamma }}_{n}$ such that ${\Sigma }_{n}^{\triangleright } \cap (2^{{\mathcal C}^{\boldsymbol {\Gamma }}_{n}})^{2} = {\Sigma }_{n}^{\boldsymbol {\Gamma }}$ and $|{\Sigma }_{n}| = \mathcal {O}(\text {poly}(n))$. We can assume that $S_{n} = \mathcal {O}(\text {poly}(n))$ and every rule in Σ_n has a form A → x, x ∈ S_n. Let R be an instance of CSP(Γ) and $x\in {\mathcal C}^{\boldsymbol {\Gamma }}_{n}$. The rule ${\mathcal C}_{\mathbf R}\to x$ is in ${\Sigma }_{n}^{\triangleright }$ if and only if x is derivable from ${\mathcal C}_{\mathbf R}$ using implications from Σ_n. Formally, the latter means that there is a directed acyclic graph T = (U,E) with a labeling function l : U → S_n such that: (a) there is only one element with no outcoming edges, the root r ∈ U, and it is labeled by x, i.e. l(r) = x, (b) every node with no incoming edges is labeled by an element of ${\mathcal C}_{\mathbf R}$, (c) if a node v ∈ U has incoming edges (c₁,v),...,(c_d(v),v), then ({l(c₁),...,l(c_d(v))}→ l(v)) ∈Σ_n. Moreover, the depth of T is bounded by |S_n|, because x can be derived from ${\mathcal C}_{\mathbf R}$ in no more than |S_n| steps if no attribute is derived twice.

Consider a monotone circuit M whose set of variables, denoted by W, consists of |S_n| layers $U_{1}, ..., U_{|S_{n}|}$ such that i-th layer is a set of variables v_i,a,a ∈ S_n. For any rule b ∈ S_n and every i ∈ [|S_n|− 1] there is a monotone logic gate

$$v_{i+1, b} = v_{i, b} \vee \bigvee\limits_{(\{a_{1}, ..., a_{l}\}\to b)\in {\Sigma}_{n}} (v_{i, a_{1}}\wedge v_{i, a_{2}}\wedge ... \wedge v_{i, a_{l}})$$

that computes the value of v_i+ 1,b from inputs of the previous layer.

Any instance R can be encoded as a Boolean vector ${\mathbf v}_{\mathbf R}\in \{0,1\}^{S_{n}}$ such that v_R(x) = 1 if and only if $x\in {\mathcal C}_{\mathbf R}$. If we set input variables of M to v_R, i.e. v_1,a := v_R(a),a ∈ S_n, then output variables of M, i.e. $v_{|S_{n}|,a}, a\in S_{n}$, will satisfy: for any $x\in {\mathcal C}^{\boldsymbol {\Gamma }}_{n}$, $v_{|S_{n}|,x}=1$ if and only if $({\mathcal C}_{\mathbf R}\to x)\in {\Sigma }_{n}^{\triangleright }$. Let us briefly outline the proof of the last statement.

Indeed, let $v_{|S_{n}|,x}=1$, $x\in {\mathcal C}_{\mathbf R}$. For any variable v_i,b ∈ W such that v_i,b = 1 let us define $\text {early}(v_{i,b}) = v_{i^{\prime },b}$ where $v_{i^{\prime },b}=1$ and $v_{i^{\prime }-1,b}=0$ and $\text {source}(v_{i,b}) = \{v_{i^{\prime }-1, a_{1}}, v_{i^{\prime }-1, a_{2}}, ... , v_{i^{\prime }-1, a_{l}}\}$ if ({a₁,...,a_l}→ b) ∈Σ_n and $v_{i^{\prime }-1, a_{1}} = 1, v_{i^{\prime }-1, a_{2}} = 1, ... , v_{i^{\prime }-1, a_{l}}=1$. Then, a rooted directed acyclic graph T_x = (U,E) with a labeling l : U → S_n can be constructed by defining U = {early(v_i,b)|v_i,b ∈ W,v_i,b = 1} and l(early(v_i,b)) = b. Edges of T_x are defined in the following way: if $v_{i^{\prime },b} = \text {early}(v_{i,b})$ and $v_{i^{\prime },b}$ was assigned to 1 by the gate $v_{i^{\prime }, b} = v_{i^{\prime }-1, b} \vee (v_{i^{\prime }-1, a_{1}}\wedge v_{i^{\prime }-1, a_{2}}\wedge ... \wedge v_{i^{\prime }-1, a_{l}})\vee \cdots$ where $\text {source}(v_{i,b}) = \{v_{i^{\prime }-1, a_{1}}, v_{i^{\prime }-1, a_{2}}, ... , v_{i^{\prime }-1, a_{l}}\}$, then we connect nodes $\text {early}(v_{i^{\prime }-1, a_{2}}), ..., \text {early}(v_{i^{\prime }-1, a_{l}})$ to $v_{i^{\prime },b}$ by incoming edges. It is easy to see that T_x will satisfy properties (a), (b), (c) listed above. The opposite is also true, if there is a directed acyclic graph with a root x that satisfies the properties (a), (b), (c), then $v_{|S_{n}|,x}=1$.

Thus, the expression $o = \bigwedge _{x\in {\mathcal C}^{\boldsymbol {\Gamma }}_{n}} v_{|S_{n}|,x}$ equals 1 if and only if $({\mathcal C}_{\mathbf R}\to {\mathcal C}_{n}^{\boldsymbol {\Gamma }}) \in {\Sigma }^{\boldsymbol {\Gamma }}_{n}$. Since Γ is not constant-preserving, the last means Hom(R,Γ) = ∅. Thus, Hom(R,Γ) = ∅ was computed by the polynomial-size monotone circuit M (with an additional gate). □

The core of Γ = {ϱ₁,...,ϱ_s} is defined as $\text {core}({\Gamma }) = \{{\varrho }_{1}\cap g(D)^{n_{1}}, ..., {\varrho }_{s}\cap g(D)^{n_{s}}\}$, the constraint language over g(D), where g ∈Hom(Γ,Γ) is such that g(x) = g(g(x)) and

$$|g(D)| = \min\limits_{h\in \text{Hom}(\boldsymbol{\Gamma}, \boldsymbol{\Gamma})} |h(D)|.$$

Corollary 1

If Γ has a weak polynomial densification operator, then core(Γ) is of bounded width.

Proof

If Γ has a weak polynomial densification operator, then by Theorem 8 ¬CSP(Γ) can be solved by a polynomial-size monotone circuit. Therefore, $\neg \text {CSP}({\Gamma }^{\prime })$ where ${\Gamma }^{\prime } = \text {core}({\Gamma })\cup \{\{(a)\}| a\in g(D)\}$ can also be solved by a polynomial-size monotone circuit. We can use the standard reduction of $\neg \text {CSP}({\Gamma }^{\prime })$ to ¬CSP(core(Γ) ∪{ρ}) where ρ ∈〈core(Γ)〉 is defined as {〈π(a)〉_a∈g(D)|π : g(D) → g(D),π ∈pol(core(Γ))}.

The algebra ${\mathbb A}_{{\Gamma }^{\prime }} = (g(D), \text {pol}({\Gamma }^{\prime }))$ generates the variety of algebras ${\textit var}({\mathbb A}_{{\Gamma }^{\prime }})$ (in the sense of Birkhoff’s HSP theorem). Proposition 5.1. from [48] states that if $\neg \text {CSP}({\Gamma }^{\prime })$ can be computed by a polynomial-size monotone circuit, then ${\textit var}({\mathbb A}_{{\Gamma }^{\prime }})$ omits both the unary and the affine type. According to a well-known result [49, 50] this is equivalent to stating that ${\Gamma }^{\prime }$ is of bounded width. □

8 Algebraic approach to the classification of languages with a polynomial densification operator

Constraint languages for which the densification problem Dense(Γ) is tractable can be classified using tools of universal algebra. An analogous approach can be applied to classify languages with a weak polynomial densification operator.

Definition 12

Let Γ = (D,ϱ₁,...,ϱ_s) and τ = {π₁,...,π_s}. A k-ary relation ρ ∈〈Γ〉 is called strongly reducible to Γ if there exists a quantifier-free primitive positive formula Ξ(x₁,⋯ ,x_n)¹ (over τ) and $\delta \subseteq D^{n}$ for some n ≥ k such that $\text {pr}_{1:k}{\Xi }^{\boldsymbol {\Gamma }}=\rho$, pr_1:kδ = D^k ∖ ρ and Ξ^Γ ∪ δ ∈〈Γ〉. A k-ary relation ρ ∈〈Γ〉 is called A-reducible to Γ if ρ = ρ₁ ∩⋯ ∩ ρ_l, where ρ_i ∈〈Γ〉 is strongly reducible to Γ for i ∈ [l].

Definition 13

A constraint language Γ is called an A-language if any ρ ∈〈Γ〉 is A-reducible to Γ.

Examples of A-languages are stated in the following theorems, whose proofs can be found in Section 14.

Theorem 9

Let Γ = (D = {0,1},ϱ₁,ϱ₂,ϱ₃) where ϱ₁ = {(x,y)|x ∨ y}, ϱ₂ = {(x,y)|¬x ∨ y} and ϱ₃ = {(x,y)|¬x ∨¬y}. Then, Γ is an A-language.

Theorem 10

Let $\boldsymbol {\Gamma } = (D=\{0,1\}, \{(0)\}, \{(1)\}, {\varrho }_{x \wedge y\rightarrow z})$ where ${\varrho }_{x \wedge y\rightarrow z} = \{(a_{1}, a_{2}, a_{3})\in D^{3}| a_{1} a_{2}\leq a_{3}\}$. Then, Γ is an A-language.

Reducibility of a relation to a language is an interesting notion because of its property stated in the following theorem.

Theorem 11

Let ${\Gamma }, {\Gamma }^{\prime }$ be constraint languages such that ${\Gamma }^{\prime }\subseteq \langle {\Gamma }\rangle$, and every relation in ${\Gamma }^{\prime }$ is A-reducible to Γ. Then:

• (a) $\text {Dense}(\boldsymbol {\Gamma }^{\prime })$ is polynomial-time Turing reducible to Dense(Γ);

• (b) if Γ has a weak polynomial densification operator, then $\boldsymbol {\Gamma }^{\prime }$ also has a weak polynomial densification operator;

• (c) if Dense(Γ) ∈mP/poly, then $\text {Dense}(\boldsymbol {\Gamma }^{\prime })\in \text {mP/poly}$.

Proof

Since ${\Gamma }^{\prime }\subseteq \langle {\Gamma }\rangle$, then there is L = {Φ_i| i ∈ [c]} where Φ_i is a primitive positive formula over the vocabulary τ = {π₁,...,π_s}, such that Γ = (D,ϱ₁,...,ϱ_s), $\boldsymbol {\Gamma }^{\prime } = (D,{\Phi }^{\boldsymbol {\Gamma }}_{1}, ..., {\Phi }^{\boldsymbol {\Gamma }}_{c})$.

Let $\mathbf {R}^{\prime } = (V,r^{\prime }_{1}, ..., r^{\prime }_{c})$ be an instance of $\text {Dense}(\boldsymbol {\Gamma }^{\prime })$. Our goal is to compute a maximal instance $(\mathbf {R}^{\prime \prime }= (V,r^{\prime \prime }_{1}, ..., r^{\prime \prime }_{c}), \boldsymbol {\Gamma }^{\prime })$ such that $r^{\prime \prime }_{i}\supseteq r^{\prime }_{i}, i\in [c]$ and $\text {Hom}(\mathbf {R}^{\prime \prime }, \boldsymbol {\Gamma }^{\prime }) = \text {Hom}(\mathbf {R}^{\prime }, \boldsymbol {\Gamma }^{\prime })$, or in other words, to compute $\text {Dense}(\mathcal {C}_{\mathbf {R}^{\prime } })$.

First, let us introduce some notations. Let Ψ be any primitive positive formula over τ, i.e. ${\Psi } = \exists x_{k+1}... x_{l} \bigwedge _{t\in [N]}\pi _{j_{t}} (x_{o_{t1}}, x_{o_{t2}}, ...)$ where j_t ∈ [s] and o_tx ∈ [l] and a = (a₁,...,a_k) be a tuple of objects. Let us introduce a set of new distinct objects NEW(a,Ψ) = {a_k+ 1,...,a_l}. Note that the sets NEW(a,Ψ) are disjoint for different (a,Ψ) (also, NEW(a,Ψ) ∩ V = ∅). For a tuple a = (a₁,...,a_k), the constraint that an assignment to (a₁,...,a_k) is in Ψ^Γ can be expressed by a collection of constraints $\mathfrak {C}({\mathbf a}, {\Psi }) = \{\langle (a_{o_{t1}}, a_{o_{t2}}, ...), {\varrho }_{j_{t}}\rangle \mid t\in [N]\}$. In other words, we require that an image of $(a_{o_{t1}}, a_{o_{t2}}, ...)$ is in ${\varrho }_{j_{t}}$ for any t ∈ [N]. Note that $\mathfrak {C}({\mathbf a}, {\Psi })$ is a set of constraints over a set of variables {a₁,...,a_k}∪NEW(Ψ,a) where only relations from Γ are allowed.

Let us start with a proof of statement (a). We will describe a reduction to Dense(Γ) that consists of two steps: first we add new variables and construct an instance of CSP(Γ) in the same way as it is done in the standard reduction of $\text {CSP}(\boldsymbol {\Gamma }^{\prime })$ to CSP(Γ); afterwards, we add new variables and constraints and form an instance of Dense(Γ).

First, for any $i\in [c],\mathbf {a}\in r^{\prime }_{i}$, we add objects NEW(a,Φ_i) to the set of variables V and define an extended set $M^{0} = V\cup \bigcup _{i\in [c],\mathbf {a}\in r^{\prime }_{i}}\text {NEW}(\mathbf {a}, {\Phi }_{i})$. Afterwards, we define a relational structure $(\mathbf {R}^{0}= (M^{0},{r^{0}_{1}}, ..., {r^{0}_{s}}), \boldsymbol {\Gamma })$ where $\mathcal {C}_{\mathbf {R}^{0}} = \bigcup _{i\in [c],\mathbf {a}\in r^{\prime }_{i}}\mathfrak {C}({\mathbf a}, {\Phi }_{i})$. By construction, $\text {pr}_{V}\text {Hom}(\mathbf {R}^{0}, \boldsymbol {\Gamma }) = \text {Hom}(\mathbf {R}^{\prime }, \boldsymbol {\Gamma }^{\prime })$. Note that this reduction is standard in the algebraic approach to fixed-template CSPs. This is the first step of the construction.

Let us now consider a relation ${\Phi }_{i}^{\boldsymbol {\Gamma }}$ and assume that its arity is k. According to the assumption, ${\Phi }_{i}^{\boldsymbol {\Gamma }}$ is A-reducible to Γ. Therefore, ${\Phi }_{i}^{\boldsymbol {\Gamma }} = {\varrho }_{i1}\cap {\cdots } \cap {\varrho }_{il}$, where ϱ_ij is strongly reducible to Γ for j ∈ [l]. Thus, there exists a quantifier-free primitive positive formula over τ, Ξ_j, involving r_j variables, and $\delta _{j}\subseteq D^{r_{j}}$, such that ${\varrho }_{ij} = \text {pr}_{1:k}{\Xi }_{j}^{\boldsymbol {\Gamma }}$ and $\text {pr}_{1:k}\delta _{j} = D^{k}\setminus {\varrho }_{ij}$ and $\delta _{j}\cup {\Xi }_{j}^{\boldsymbol {\Gamma }}\in \langle {\Gamma }\rangle$. Since $\gamma _{j} = \delta _{j}\cup {\Xi }_{j}^{\boldsymbol {\Gamma }}$ is pp-definable over Γ, there exists a primitive positive formula over τ, $\exists x_{r_{j}+1}\cdots x_{p_{j}}{\Theta }_{j} (x_{1}, \cdots , x_{p_{j}})$ where Θ_j is quantifier-free, such that $(\exists x_{r_{j}+1}{\cdots } x_{p_{j}}{\Theta }_{j} (x_{1}, \cdots , x_{p_{j}}))^{\boldsymbol {\Gamma }} = \delta _{j}\cup {\Xi }_{j}^{\boldsymbol {\Gamma }}$. Let us introduce a set of constraints:

$$ \mathfrak{C}(V, {\Phi}_{i}) = \bigcup\limits_{(a_{1}, ..., a_{k})\in V^{k}} \bigcup\limits_{j\in [l]} \mathfrak{C}\big((a_{1}, ..., a_{k}), \exists x_{k+1}, \cdots,x_{p_{j}}{\Theta}_{j} (x_{1}, \cdots, x_{p_{j}})\big). $$

over a set of variables

$$M_{i} = V\cup \bigcup\limits_{(a_{1}, ..., a_{k})\in V^{k}} \bigcup\limits_{j\in [l]} \text{NEW}\big((a_{1}, ..., a_{k}), \exists x_{k+1}, \cdots,x_{p_{j}}{\Theta}_{j} (x_{1}, \cdots, x_{p_{j}})).$$

Due to $\text {pr}_{1:k}\delta _{j} = D^{k}\setminus {\varrho }_{ij}$, we have $\text {pr}_{1:k} (\delta _{j}\cup {\Xi }_{j}^{\boldsymbol {\Gamma }}) = D^{k}$. Therefore,

$$(\exists x_{k+1}{\cdots} x_{p_{j}} {\Theta}_{j} (x_{1}, \cdots, x_{p_{j}}))^{\boldsymbol{\Gamma}} = \text{pr}_{1:k}(\delta_{j}\cup {\Xi}_{j}^{\boldsymbol{\Gamma}}) = D^{k}.$$

Thus, the set of constraints $\mathfrak {C}(V, {\Phi }_{i})$ does not add any restrictions on assignments of V (though it adds restrictions on additional variables).

Let R = (M,r₁,...,r_s) be such that $M = V \cup \bigcup _{i\in [c],\mathbf {a}\in r^{\prime }_{i}}\text {NEW}({\mathbf a}, {\Phi }_{i}) \bigcup _{i\in [c]} M_{i}$ and $\mathcal {C}_{\mathbf {R}} = \bigcup _{i\in [c],\mathbf {a}\in r^{\prime }_{i}}\mathfrak {C}({\mathbf a}, {\Phi }_{i}) \bigcup _{i\in [c]} \mathfrak {C}(V, {\Phi }_{i})$. By construction, $\text {pr}_{V}\text {Hom}(\mathbf {R}, \boldsymbol {\Gamma }) = \text {Hom}(\mathbf {R}^{\prime }, \boldsymbol {\Gamma }^{\prime })$. Let us treat R as an instance of Dense(Γ).

The computation of $\text {Dense}(\mathcal {C}_{\mathbf {R}^{\prime }})$ can be made by checking whether $\langle (v_{1},\cdots , v_{k}), {\Phi }^{\boldsymbol {\Gamma }}_{i} \rangle \in \text {Dense}(\mathcal {C}_{\mathbf {R}^{\prime }})$ for any v₁,⋯ ,v_k ∈ V and a k-ary ${\Phi }^{\boldsymbol {\Gamma }}_{i}\in {\Gamma }$. From the following lemma it follows that such a checking can be reduced to a checking of certain conditions of the form $\langle (u_{1}, u_{2}, ...), {\varrho }_{j}\rangle \in \text {Dense}(\mathcal {C}_{\mathbf {R}})$, i.e. to the computation of $\text {Dense}(\mathcal {C}_{\mathbf {R}})$.

Lemma 1

For a k-ary ${\Phi }^{\boldsymbol {\Gamma }}_{i}$ and v₁,⋯ ,v_k ∈ V there is a subset $S_{i}(v_{1},\cdots , v_{k}) \subseteq \mathcal {C}^{\boldsymbol {\Gamma }}_{M}$ (that can be computed in time poly(|V |)) such that the condition $\langle (v_{1},\cdots , v_{k}), {\Phi }^{\boldsymbol {\Gamma }}_{i} \rangle \in \text {Dense}(\mathcal {C}_{\mathbf {R}^{\prime }}) (\subseteq \mathcal {C}^{\boldsymbol {\Gamma }^{\prime }}_{V})$ is equivalent to a list of conditions $\langle (u_{1}, u_{2}, ...), {\varrho }_{j}\rangle \in \text {Dense}(\mathcal {C}_{\mathbf {R}}) (\subseteq \mathcal {C}^{\boldsymbol {\Gamma }}_{M})$ for 〈(u₁,u₂,...),ϱ_j〉∈ S_i(v₁,⋯ ,v_k).

Proof

Note that $\langle (v_{1},\cdots , v_{k}), {\Phi }^{\boldsymbol {\Gamma }}_{i} \rangle \in \text {Dense}(\mathcal {C}_{\mathbf {R}^{\prime }})\subseteq \mathcal {C}^{\boldsymbol {\Gamma }^{\prime }}_{V}$ for v₁,⋯ ,v_k ∈ V if and only if $\text {pr}_{v_{1},\cdots , v_{k}} \text {Hom}(\mathbf {R}, \boldsymbol {\Gamma })\subseteq {\Phi }^{\boldsymbol {\Gamma }}_{i}$. Let us assume that we have $\text {pr}_{v_{1},\cdots , v_{k}} \text {Hom}(\mathbf {R}, \boldsymbol {\Gamma })\subseteq {\Phi }^{\boldsymbol {\Gamma }}_{i}$. The definition of R implies that we have a set of constraints

$$\mathfrak{C} ((v_{1}, ..., v_{k}), \exists x_{k+1}, \cdots,x_{p_{j}}{\Theta}_{j} (x_{1}, \cdots, x_{p_{j}}))$$

imposed on v₁,⋯ ,v_k and

$$\text{NEW}\big((v_{1}, ..., v_{k}), \exists x_{k+1}, \cdots,x_{p_{j}}{\Theta}_{j} (x_{1}, \cdots, x_{p_{j}})) = \{v_{k+1},\cdots, v_{p_{j}}\}$$

(how Φ_i and Θ_j,j ∈ [l] are related is described above). Since ${\Phi }_{i}^{\boldsymbol {\Gamma }} = {\varrho }_{i1}\cap {\cdots } \cap {\varrho }_{il}$, we conclude $\text {pr}_{v_{1},\cdots , v_{k}} \text {Hom}(\mathbf {R}, \boldsymbol {\Gamma })\subseteq {\varrho }_{ij}, j\in [l]$. Therefore, $\text {pr}_{v_{1},\cdots , v_{p_{j}}} \text {Hom}(\mathbf {R}, \boldsymbol {\Gamma })\subseteq \{{\mathbf x}\in {\Theta }_{j}^{\boldsymbol {\Gamma }} \mid {\mathbf x}_{1:k}\in {\varrho }_{ij}\}$, that is $\text {pr}_{v_{1},\cdots , v_{r_{j}}} \text {Hom}(\mathbf {R}, \boldsymbol {\Gamma })\subseteq \{{\mathbf x}_{1:r_{j}}\mid {\mathbf x}\in {\Theta }_{j}^{\boldsymbol {\Gamma }}, {\mathbf x}_{1:k}\in {\varrho }_{ij}\} = {\Xi }_{j}^{ \boldsymbol {\Gamma }}$. Since Ξ_j is a quantifier-free primitive positive formula over τ, then the fact $\text {pr}_{v_{1},\cdots , v_{r_{j}}} \text {Hom}(\mathbf {R}, \boldsymbol {\Gamma })\subseteq {\Xi }_{j}^{\boldsymbol {\Gamma }}$ can be expressed as $(h(v_{1}),\cdots , h(v_{r_{j}}))\in {\Xi }^{\boldsymbol {\Gamma }}_{j}$ for any h ∈Hom(R,Γ). In other words, if ${\Xi }_{j} = \exists x_{k+1}... x_{l} \bigwedge _{t\in [N]}\pi _{w_{t}} (x_{o_{t1}}, x_{o_{t2}}, ...)$, then $\langle (v_{o_{t1}}, v_{o_{t2}}, ...), {\varrho }_{w_{t}}\rangle \in \text {Dense}(\mathcal {C}_{\mathbf {R}})\subseteq \mathcal {C}^{\boldsymbol {\Gamma }}_{V}$ for any t ∈ [N]. Let us set

$$ S_{i}(v_{1},\cdots, v_{k}) = \{\langle (v_{o_{t1}}, v_{o_{t2}}, ...), {\varrho}_{w_{t}}\rangle \mid {\Xi}_{j} = \exists x_{k+1}... x_{l} \bigwedge_{t\in [N]}\pi_{w_{t}} (x_{o_{t1}}, x_{o_{t2}}, ...), j\in [l]\} $$

In fact, we proved

$$ \langle (v_{1},\cdots, v_{k}), {\Phi}^{\boldsymbol{\Gamma}}_{i} \rangle\in \text{Dense}(\mathcal{C}_{\mathbf{R}^{\prime}}) \Rightarrow S_{i}(v_{1},\cdots, v_{k})\subseteq \text{Dense}(\mathcal{C}_{\mathbf{R}}).$$

It can be easily checked that the last chain of arguments can be reversed, and

$$S_{i}(v_{1},\cdots, v_{k})\subseteq \text{Dense}(\mathcal{C}_{\mathbf{R}})\Rightarrow \langle (v_{1},\cdots, v_{k}), {\Phi}^{\boldsymbol{\Gamma}}_{i} \rangle\in \text{Dense}(\mathcal{C}_{\mathbf{R}^{\prime}}). $$

□

Thus, statement (a) is proved.

Statement (b) directly follows from the previous reduction. Suppose Γ has a weak polynomial densification operator, i.e. there is a finite $S_{n}\supseteq \mathcal {C}_{n}^{\boldsymbol {\Gamma }}$ and an implicational system ${\Delta }_{n} \subseteq 2^{S_{n}}\times 2^{S_{n}}$ of size $|{\Delta }_{n}| = {\mathcal O}(\text {poly}(n))$ that acts on ${\mathcal C}^{\boldsymbol {\Gamma }}_{n}$ as the densification operator, i.e. ${\Sigma }_{n}^{\boldsymbol {\Gamma }} = \{(A\rightarrow B)\in {\Delta }_{n}^{\triangleright }| A,B\subseteq {\mathcal C}^{\boldsymbol {\Gamma }}_{n}\}$.

If V = [n], then $X = V \cup \bigcup _{i\in [c],\mathbf {a}=(a_{1},a_{2}, \cdots ,), a_{i}\in V}\text {NEW}({\mathbf a}, {\Phi }_{i}) \bigcup _{i\in [c]} M_{i}$ (M_i are defined above) is a superset of V whose size is bounded by a polynomial of n. Therefore, w.l.o.g. we can assume X = [m] where $m=|X|={\mathcal O}(\text {poly} (n))$. Let Δ_m be an implicational system on $S_{m}\supseteq {\mathcal C}^{\boldsymbol {\Gamma }}_{m}$ such that $|{\Delta }_{m}| = {\mathcal O}(\text {poly} (m))$ and $o_{{\Delta }_{m}}(S) = \{x\in {\mathcal C}^{\boldsymbol {\Gamma }}_{m} | (S\rightarrow x)\in {\Delta }_{m}^{\triangleright }\}$ acts as the densification operator on subsets of ${\mathcal C}^{\boldsymbol {\Gamma }}_{m}$. Since ${\Delta }_{m}\subseteq 2^{S_{m}} \times 2^{S_{m}}$, we can interpret Δ_m as an implicational system on $S^{\prime }_{m} = S_{m}\cup {\mathcal C}^{\boldsymbol {{\Gamma }^{\prime }}}_{n}$, i.e. we include ${\mathcal C}^{\boldsymbol {{\Gamma }^{\prime }}}_{n}$ into a set of literals of Δ_m. Let us now add to Δ_m new implications by the following rule: for ${\Phi }_{i} = \exists x_{k+1}... x_{l} \bigwedge _{t\in [N]}\pi _{j_{t}} (x_{o_{t1}}, x_{o_{t2}}, ...)$, a ∈ [n]^k and the corresponding new l − k variables NEW(a,Φ_i) = {a_k+ 1,...,a_l} we add $R(\mathbf {a}, {\Phi }_{i}): \langle \mathbf {a}, {\Phi }_{i}^{\boldsymbol {\Gamma }} \rangle \rightarrow \{\langle (a_{o_{t1}}, a_{o_{t2}}, ...), {\varrho }_{j_{t}} \rangle | t\in [N]\}$. Let us denote

$$ \mathfrak{R}_{1} = \bigcup\limits_{i\in [c], \mathbf{a} = (a_{1}, a_{2},...): a_{i}\in V} \{R(\mathbf{a}, {\Phi}_{i})\}. $$

The second kind of implications that we need to add to Δ_m is

$$ \mathfrak{R}_{2} = \bigcup\limits_{i\in [c]}\{\emptyset \to \mathfrak{C}(V, {\Phi}_{i}) \}. $$

The last set of implications, $\mathfrak {R}_{3}$, is defined by

$$\mathfrak{R}_{3} = \{(S_{i}(v_{1},\cdots, v_{k}) \to \langle (v_{1},\cdots, v_{k}), {\Phi}^{\boldsymbol{\Gamma}}_{i}\rangle )\mid \langle (v_{1},\cdots, v_{k}), {\Phi}^{\boldsymbol{\Gamma}}_{i}\rangle \in \mathcal{C}^{\boldsymbol{\Gamma}^{\prime}}_{n}\},$$

where S_i(v₁,⋯ ,v_k) is described in the previous Lemma, i.e. it equals a set of constraints for which $S_{i}(v_{1},\cdots , v_{k})\subseteq \text {Dense}(\mathcal {C}_{\mathbf {R}})$ is equivalent to $\langle (v_{1},\cdots , v_{k}), {\Phi }^{\boldsymbol {\Gamma }}_{i}\rangle \in \text {Dense}(\mathcal {C}_{\mathbf {R}^{\prime }})$. Thus, we defined a set of implications ${\Delta }_{m}\cup \mathfrak {R}_{1}\cup \mathfrak {R}_{2} \cup \mathfrak {R}_{3}$. Let us denote a new system by Σ_n. By the construction of Σ_n, we have $|{\Sigma }_{n}| = {\mathcal O}(\text {poly} (n))$.

Given $\mathcal {C}_{\mathbf {R}^{\prime }}$, using implications from $\mathfrak {R}_{1}$, one can derive the set of constraints $\mathcal {C}_{\mathbf {R}^{0}}$ (R⁰ is defined above), and using implications from $\mathfrak {R}_{2}$ one completes the set of derivable literals to $\mathcal {C}_{\mathbf {R}}$. Then, using initial rules of Δ_m, one can derive from $\mathcal {C}_{\mathbf {R}}$ its closure $\text {Dense}(\mathcal {C}_{\mathbf {R}})$. Finally, using implications from $\mathfrak {R}_{3}$ one can derive all constraints from $\text {Dense}(\mathcal {C}_{\mathbf {R}^{\prime }})$. It is not hard to prove that $x\in \mathcal {C}_{n}^{\boldsymbol {\Gamma }^{\prime }}$ is derivable from $\mathcal {C}_{\mathbf {R}^{\prime }}$ if and only if $x\in \text {Dense}(\mathcal {C}_{\mathbf {R}^{\prime }})$.

Thus, $\boldsymbol {\Gamma }^{\prime }$ also has a weak polynomial densification operator. Note that implications $\mathfrak {R}_{2} \cup \mathfrak {R}_{3}$ are all from ${\Sigma }^{\boldsymbol {\Gamma \cup {\Gamma }^{\prime }}}_{m}$, but an implication $R(\mathbf {a}, {\Phi }_{i})\in \mathfrak {R}_{1}$ is not, in general, from ${\Sigma }^{\boldsymbol {\Gamma \cup {\Gamma }^{\prime }}}_{m}$.

Statement (c) directly follows from the fact that the function $Q: 2^{\mathcal {C}^{{\mathbf {\Gamma }}^{\prime }}_{V}}\to 2^{\mathcal {C}^{\mathbf {\Gamma }}_{M}}$ such that $Q(C_{{\mathbf R}^{\prime }})=C_{\mathbf R}$ is monotone and can be computed by a polynomial-size monotone circuit. □

9 DS-basis and algorithms for Dense(Γ) and Sparse(Γ)

The notion of DS-basis is a formalization of templates for which a small cover of ${\Sigma }_{n}^{\boldsymbol {\Gamma }}$ not only exists but can also be computed efficiently.

Definition 14

A fixed template Γ is called a DS-basis, if there exists an algorithm $\mathcal {A}$ that solves in time ${\mathcal O}(\text {poly}(n))$ the task with:

• An instance: a natural number $n\in {\mathbb N}$;

• An output: an implicational system ${\Sigma }\subseteq {\Sigma }_{n}^{\boldsymbol {\Gamma }}$ such that ${\Sigma }^{\triangleright }= {\Sigma }_{n}^{\boldsymbol {\Gamma }}$.

Theorem 12

For any DS-basis Γ there is an algorithm $\mathcal {A}_{1}$ that, given an instance R of Dense(Γ), solves the densification problem for (R,Γ) in time ${\mathcal O}(\text {poly}(|V|))$.

Proof

For any implicational system ${\Sigma }\subseteq 2^{S} \times 2^{S}$, and any $A,B\subseteq S$, the membership $A\rightarrow B \mathop \in \limits ^{?} {\Sigma }^{\triangleright }$ can be checked in time ${\mathcal O}(|{\Sigma }|)$ by Beeri and Bernstein’s algorithm for functional dependencies [51].

Since Γ is the DS-basis, then there exists an algorithm $\mathcal {A}$ using which one can compute in time ${\mathcal O}(\text {poly}(|V|))$ an implicational system ${\Sigma }\subseteq {\Sigma }_{V}^{\boldsymbol {\Gamma }}$ such that ${\Sigma }^{\triangleright } = {\Sigma }_{V}^{\boldsymbol {\Gamma }}$. Afterwards, we check whether $\mathcal {C}_{\mathbf {R}}\rightarrow x\mathop \in \limits ^{?} {\Sigma }_{V}^{\boldsymbol {\Gamma }}$ using Beeri and Bernstein’s algorithm for any $x\in \mathcal {C}^{\boldsymbol {\Gamma }}_{V}$ and compute $\text {Dense} (\mathcal {C}_{\mathbf {R}}) = \{x\in \mathcal {C}^{\boldsymbol {\Gamma }}_{V}| \mathcal {C}_{\mathbf {R}}\rightarrow x\in {\Sigma }^{\triangleright }\}$ in time ${\mathcal O}(|\mathcal {C}^{\boldsymbol {\Gamma }}_{V}|\cdot |{\Sigma }|) = {\mathcal O}(\text {poly}(|V|))$. Finally we set $r^{\prime }_{i} = \{(v_{1}, ..., v_{\|{\varrho }_{i}\|}) | \langle (v_{1}, ..., v_{\|{\varrho }_{i}\|}), {\varrho }_{i}\rangle \in \text {Dense} (\mathcal {C}_{\mathbf {R}})\}$ for i ∈ [s]. The instance $(\mathbf {R}^{\prime }= (V,r^{\prime }_{1}, ..., r^{\prime }_{s}), \boldsymbol {\Gamma })$ is maximal. □

The following theorem is equivalent to Theorem 7 announced in Section 6.

Theorem 13

For any DS-basis Γ there is an algorithm $\mathcal {A}_{2}$ that, given an instance R of Sparse(Γ), solves the sparsification problem for (R,Γ) in time ${\mathcal O} (\text {poly}(|V|)\cdot |\text {Min} (\mathbf {R}, \boldsymbol {\Gamma })|^{2})$.

Proof

It is easy to see that a set of all possible instances of Sparse(Γ), {R = (V,⋯ )}, is in one-to-one correspondence with a set $2^{\mathcal {C}^{\boldsymbol {\Gamma }}_{V}}$. For any implicational system F on S, let us call $A\subseteq S$ a minimal key of F for B if $(A\rightarrow B)\in F^{\triangleright }$, but for any proper subset C ⊂ A, $(C\rightarrow B)\notin F^{\triangleright }$. Let us prove first that $\mathbf {R}^{\prime }\in \text {Min} (\mathbf {R}, \boldsymbol {\Gamma })$ is and only if $\mathcal {C}_{\mathbf {R}^{\prime }}$ is a minimal key of ${\Sigma }^{\boldsymbol {\Gamma }}_{V}$ for $\text {Dense} (\mathcal {C}_{\mathbf {R}})$.

Indeed, if $\mathbf {R}^{\prime }\in \text {Min} (\mathbf {R}, \boldsymbol {\Gamma })$, then $\text {Hom}(\mathbf {R}, \boldsymbol {\Gamma })= \text {Hom}(\mathbf {R}^{\prime }, \boldsymbol {\Gamma })$. Since $\text {Hom}(\mathbf {R}, \boldsymbol {\Gamma })= \text {Hom}(\mathbf {R}^{\prime }, \boldsymbol {\Gamma })$, then $\text {Dense} (\mathcal {C}_{\mathbf {R}}) = \text {Dense} (\mathcal {C}_{\mathbf {R}^{\prime }})$ (by the definition of the densification operator). Therefore, from the duality between the closure operator Dense and the implication system ${\Sigma }_{V}^{\boldsymbol {\Gamma }}$ we obtain $(\mathcal {C}_{\mathbf {R}^{\prime }} \rightarrow \text {Dense} (\mathcal {C}_{\mathbf {R}}))\in {\Sigma }_{V}^{\boldsymbol {\Gamma }}$. Since the pair $(\mathbf {R}^{\prime }, \boldsymbol {\Gamma })$ is minimal, we obtain that $\mathcal {C}_{\mathbf {R}^{\prime }}$ is a minimal key for $\text {Dense} (\mathcal {C}_{\mathbf {R}})$.

On the contrary, let $\mathcal {C}_{\mathbf {R}^{\prime }}$ be a minimal key for $\text {Dense} (\mathcal {C}_{\mathbf {R}})$. Therefore, $\text {Dense} (\mathcal {C}_{\mathbf {R}}) = \text {Dense} (\mathcal {C}_{\mathbf {R}^{\prime }})$, from which we obtain $\text {Hom}(\mathbf {R}, \boldsymbol {\Gamma })= \text {Hom}(\mathbf {R}^{\prime }, \boldsymbol {\Gamma })$. Any proper subset $\mathcal {C}_{\mathbf {R}^{\prime \prime }}\subset \mathcal {C}_{\mathbf {R}^{\prime }}$ has a closure $\text {Dense} (\mathcal {C}_{\mathbf {R}^{\prime \prime }})\subset \text {Dense} (\mathcal {C}_{\mathbf {R}^{\prime }})$. Thus, we obtain that $\text {Hom}(\mathbf {R}^{\prime }, \boldsymbol {\Gamma })\ne \text {Hom}(\mathbf {R}^{\prime \prime }, \boldsymbol {\Gamma })$ (otherwise, we have $\text {Dense} (\mathcal {C}_{\mathbf {R}^{\prime \prime }}) = \text {Dense} (\mathcal {C}_{\mathbf {R}^{\prime }})$). We conclude that the pair $(\mathbf {R}^{\prime }, \boldsymbol {\Gamma })$ is minimal.

Since Γ is a DS-basis, we construct in advance an implicational system ${\Sigma }\subseteq {\Sigma }_{V}^{\boldsymbol {\Gamma }}$ such that ${\Sigma }^{\triangleright } = {\Sigma }_{V}^{\boldsymbol {\Gamma }}$. We proved that the problem of listing of Min(R,Γ) is equivalent to a listing of all minimal keys for $\text {Dense} (\mathcal {C}_{\mathbf {R}})$ in the implicational system Σ. In database theory, this task is called the optimal cover problem and was studied in the 70s [52]. The algorithm of Luchessi and Osborn lists all minimal keys for $\text {Dense} (\mathcal {C}_{\mathbf {R}})$ in time $\mathcal {O}(|{\Sigma }|\cdot |\text {Min} (\mathbf {R}, \boldsymbol {\Gamma })| \cdot |\text {Dense} (\mathcal {C}_{\mathbf {R}})| \cdot (|\text {Min} (\mathbf {R}, \boldsymbol {\Gamma })|+|\text {Dense} (\mathcal {C}_{\mathbf {R}})|))$ (see p. 274 of [26]). It is easy to see that the last expression is bounded by ${\mathcal O} (\text {poly}(|V|)\cdot |\text {Min} (\mathbf {R}, \boldsymbol {\Gamma })|^{2})$.

Note that main approaches to listing minimal keys in a functional dependency table refer to the method of Luchessi and Osborn. Nowadays, several alternative methods are designed for this and adjacent tasks [53], including efficient parallelization techniques [54]. □

Remark 2

Sometimes we are interested not in Min(R,Γ), but in its subset $\text {Min}(\mathbf {R}, \boldsymbol {\Gamma }, S) = \{\mathbf {R}^{\prime }\in \text {Min}(\mathbf {R}, \boldsymbol {\Gamma }) \mid \mathcal {C}_{\mathbf {R}^{\prime }}\subseteq S\}$ where $S\subseteq \mathcal {C}_{V}^{\boldsymbol {\Gamma }}$. For example, if $S=\mathcal {C}_{\mathbf {R}}$, then listing Min(R,Γ,S) is equivalent to a listing of all non-redundant sparsifications that are subsets of the set of initial constraints. The latter set could have a substantially smaller cardinality than Min(R,Γ). A natural approach to list Min(R,Γ,S) is to compute a cover ${\Sigma }^{\prime }$ of ${\Sigma }_{V}^{\boldsymbol {\Gamma }}\cap (2^{S})^{2}= {\Sigma }^{\triangleright }\cap (2^{S})^{2}$ and then list minimal keys of ${\Sigma }^{\prime }$ for S (sometimes called candidate keys) by the method of Luchessi and Osborn in time $\mathcal {O}(|{\Sigma }^{\prime }|\cdot |\text {Min} (\mathbf {R}, \boldsymbol {\Gamma }, S)| \cdot |S| \cdot (|\text {Min} (\mathbf {R}, \boldsymbol {\Gamma }, S)|+|S|))$. For the computation of ${\Sigma }^{\prime }$, it is natural to exploit the Reduction by Resolution algorithm (RBR) suggested in [55]. The bottleneck of that strategy is that a small cover of ${\Sigma }^{\triangleright }\cap (2^{\mathcal {C}_{\mathbf {R}}})^{2}$ may not exist. In such cases RBR’s computation takes a long time that can be potentially exponential.

Next, we will show that DS-bases include such templates for which Dense(Γ) can be solved by a Datalog program.

10 Densification by Datalog program

The idea of using Datalog programs for CSP is classical [1, 56, 57].

Definition 15

If ${\Phi }(x_{1}, ..., x_{n_{u}})$ is a primitive positive formula over τ, then the first-order formula

$${\Psi} = \forall x_{1}, ..., x_{n_{u}} \big({\Phi} (x_{1}, ..., x_{n_{u}})\rightarrow \pi_{u} (x_{1}, ..., x_{n_{u}})\big)$$

is called a Horn formula² over τ. If a primitive positive definition of Φ involves n variables, then Ψ is said to be of width (n_u,n) (or, simply, of width n). Any Horn formula of width (n_u,n) is equivalent to the universal formula

$$\forall x_{1}, ..., x_{n} \big(\bigwedge\limits_{t=1}^{N} \pi_{j_{t}} (x_{o_{t1}}, x_{o_{t2}}, ..., x_{o_{tn_{j_{t}}}})\rightarrow \pi_{u} (x_{1}, ..., x_{n_{u}})\big),$$

so we will refer to both of them as Horn formulas. For a relational structure R = (V,r₁,...,r_s), ∥r_i∥ = n_i, $\mathbf {R}\vDash {\Psi }$ denotes ${\Phi }^{\mathbf {R}}\subseteq r_{u}$.

For the densification task, the use of Datalog is motivated by the following theorem.

Theorem 14

Let (R,Γ) be a maximal instance of CSP. For any Horn formula Ψ, if $\boldsymbol {\Gamma }\vDash {\Psi }$, then $\mathbf {R}\vDash {\Psi }$.

Proof

Let Γ = (D,ϱ₁,...,ϱ_s) and

$${\Psi} = \forall x_{1}, ..., x_{n_{u}} \exists x_{n_{u}+1}... x_{n} {\Xi}(x_{1}, ..., x_{n})\rightarrow \pi_{u}(x_{1}, ..., x_{n_{u}})$$

where

$${\Xi}(x_{1}, ..., x_{n}) = \bigwedge\limits_{t=1}^{N} \pi_{j_{t}} (x_{o_{t1}}, x_{o_{t2}}, ..., x_{o_{tn_{j_{t}}}})$$

such that $\boldsymbol {\Gamma }\vDash {\Psi }$. Let $h: V\rightarrow D$ be any mapping and $r_{i} = h^{-1}({\varrho }_{i})$. Let us prove that $\mathbf {R}\vDash {\Psi }$ where R = (V,r₁,...,r_s).

Indeed, for any a ∈ r_i we have h(a) ∈ ϱ_i, i ∈ [s]. From $\boldsymbol {\Gamma }\vDash {\Psi }$ we obtain that the following statement is true: if there exist a₁,...,a_n ∈ D such that $(a_{o_{t1}}, a_{o_{t2}}, ..., a_{o_{tn_{j_{t}}}})\in {\varrho }_{j_{t}}$, t ∈ [N], then $(a_{1}, ..., a_{n_{u}})\in {\varrho }_{u}$.

Suppose now that we are given b₁,...,b_n ∈ V such that for any t ∈ [N] we have $(b_{o_{t1}}, b_{o_{t2}}, ..., b_{o_{tn_{j_{t}}}})\in r_{j_{t}}$. Therefore, for any t ∈ [N] we have

$$ (h(b_{o_{t1}}), h(b_{o_{t2}}), ..., h(b_{o_{tn_{j_{t}}}}))\in {\varrho}_{j_{t}}.$$

From $\boldsymbol {\Gamma }\vDash {\Psi }$ we obtain that $(h(b_{1}), ..., h(b_{n_{u}}))\in {\varrho }_{u}$. Therefore, $(b_{1}, ..., b_{n_{u}})\in r_{u}$. Thus, we proved $\mathbf {R}\vDash {\Psi }$.

Finally, let (R,Γ) be a maximal instance of CSP and R = (V,r₁,...,r_s). By the definition of the maximal instance, we have $r_{i}=\bigcap _{h\in \text {Hom}(\mathbf {R}, \boldsymbol {\Gamma })} h^{-1}({\varrho }_{i})$. Horn formulas have the following simple property: if $(V,{r^{1}_{1}}, ..., {r^{1}_{s}})\vDash {\Psi }$ and $(V,{r^{2}_{1}}, ..., {r^{2}_{s}})\vDash {\Psi }$, then $(V,{r^{1}_{1}}\cap {r^{2}_{1}}, ..., {r^{1}_{s}}\cap {r^{2}_{s}})\vDash {\Psi }$. Since $(V, h^{-1}({\varrho }_{1}), ..., h^{-1}({\varrho }_{s}))\vDash {\Psi }$ for any h ∈Hom(R,Γ), we conclude $\mathbf {R}\vDash {\Psi }$. □

Theorem 14 motivates the following approach to the problem Dense(Γ). Let L = {Ψ₁,...,Ψ_c} be a finite set of Horn formulas such that $\boldsymbol {\Gamma }\vDash {\Psi }_{i}$, i ∈ [c]. Given an instance R = (V,r₁,...,r_s) of Dense(Γ), let us define an operator

$$ q_{i}(r_{1}, ..., r_{s}) = r_{i} \cup\bigcup\limits_{\Psi\in L: {\Psi} = \forall x_{1:n_{i}}({\Phi}(x_{1}, ..., x_{n_{i}})\rightarrow \pi_{i}(x_{1}, ..., x_{n_{i}}))}{\Phi}^{\mathbf{R}}, $$

called the immediate consequence operator, i.e. it outputs a single application of the rules that contain π_i as the head. This induces an operator on relational structures:

$$ Q(\mathbf{R}) = (V, q_{1}(r_{1}, ..., r_{s}), ..., q_{s}(r_{1}, ..., r_{s})) $$

Since $q_{i}(r_{1}, ..., r_{s})\supseteq r_{i}$, the Algorithm (2) eventually stops at the fixed point of the operator Q(R), i.e. at Q^K− 1(R) where:

$$ \mathbf{R}^{0} = \mathbf{R}, \mathbf{R}^{k} = Q (\mathbf{R}^{k-1}), k\in [K], \mathbf{R}^{K} = \mathbf{R}^{K-1}. $$

(2)

In that algorithm we iteratively add new tuples to predicates r_i,i ∈ [s] until all Horn formulas in L are satisfied.

Let us denote the output Q^K− 1(R) of the Algorithm (2) by $\mathbf {R}^{L} = (V,{r^{L}_{1}}, ..., {r^{L}_{s}})$. In fact, the Algorithm (2) calculates the fixed point of the operator Q(R) in O(|R^L|) iterations, where $|\mathbf {R}^{L}| = {\sum }_{i=1}^{s} |{r^{L}_{i}}|$. It is easy to see that $\mathbf {R}^{L} = (V,{r^{L}_{1}}, ..., {r^{L}_{s}})$ is a smallest (w.r.t. inclusion) relational structure T = (V,t₁,...,t_s) such that $t_{i}\supseteq r_{i}, i\in [s]$ and $\mathbf {T} \vDash {\Psi }_{i}$, i ∈ [c]. Therefore, R^L is a good candidate for a maximal instance $(\mathbf {R}^{\prime }= (V,r^{\prime }_{1}, ..., r^{\prime }_{s}), \boldsymbol {\Gamma })$, $r^{\prime }_{i}\supseteq r_{i}, i\in [s]$.

Definition 16

Let τ be a vocabulary and F∉τ be a stop symbol with an arity 0 assigned to it. Let L be a finite set of Horn formulas over τ such that Γ⊧Ψ,Ψ ∈ L and L^stop be a finite set of formulas of the form Φ →F where Φ is a quantifier-free primitive positive formula over τ. It is said that Dense(Γ) can be solved by the Datalog program L ∪ L^stop, if for any instance R of Dense(Γ), we have: (a) if Hom(R,Γ)≠∅, then (R^L,Γ) is maximal and ${\Phi }^{\mathbf {R}^{L}}= \emptyset$ for any (Φ →F) ∈ L^stop, and (b) if Hom(R,Γ) = ∅, then there is (Φ →F) ∈ L^stop such that ${\Phi }^{\mathbf {R}^{L}}\ne \emptyset$.

Theorem 15

If Dense(Γ) can be solved by the Datalog program L ∪ L^stop, then Γ is a DS-basis.

Proof

Any Ψ ∈ L can be represented as

$${\Psi} = \forall x_{1}, ..., x_{n} \big(\bigwedge\limits_{t=1}^{N} \pi_{j_{t}} (x_{o_{t1}}, x_{o_{t2}}, ..., x_{o_{tn_{j_{t}}}})\rightarrow \pi_{u} (x_{1}, ..., x_{n_{u}})\big). $$

For any sequence v₁,...,v_n ∈ V let us introduce an implication

$$ R_{\Psi}(v_{1}, ..., v_{n}) \rightarrow \langle (v_{1}, ..., v_{n_{u}}), {\varrho}_{u}\rangle $$

(3)

where $R_{\Psi }(v_{1}, ..., v_{n}) = \big \{ \langle (v_{o_{t1}}, v_{o_{t2}}, ..., v_{o_{tn_{j_{t}}}}), {\varrho }_{j_{t}}\rangle | t\in [N] \big \} \subseteq \mathcal {C}^{\boldsymbol {\Gamma }}_{V}$. Analogously, any Ψ ∈ L^stop can be represented as ${\Psi } = \big (\bigwedge _{t=1}^{N} \pi _{j_{t}} (x_{o_{t1}}, x_{o_{t2}}, ..., x_{o_{tn_{j_{t}}}})\rightarrow \mathrm {F}\big )$ and we define an implication

$$ R_{\Psi}(v_{1}, ..., v_{n}) \rightarrow {\mathcal C}^{\boldsymbol{\Gamma}}_{V} $$

(4)

where $R_{\Psi }(v_{1}, ..., v_{n}) = \big \{ \langle (v_{o_{t1}}, v_{o_{t2}}, ..., v_{o_{tn_{j_{t}}}}), {\varrho }_{j_{t}}\rangle | t\in [N] \big \} \subseteq \mathcal {C}^{\boldsymbol {\Gamma }}_{V}$.

Let us denote

$$ \begin{array}{llllll} {\Omega}^{V}_{\Psi} = \bigcup\limits_{v_{1}, ..., v_{n}\in V}\{R_{\Psi}(v_{1}, ..., v_{n}) \rightarrow \langle (v_{1}, ..., v_{n_{u}}), {\varrho}_{u}\rangle\} \end{array} $$

(5)

if Ψ ∈ L and

$$ \begin{array}{llllll} {\Omega}^{V}_{\Psi} = \bigcup\limits_{v_{1}, ..., v_{n}\in V}\{R_{\Psi}(v_{1}, ..., v_{n}) \rightarrow \mathcal{C}^{\boldsymbol{\Gamma}}_{V}\} \end{array} $$

if Ψ ∈ L^stop and set

$$ {\Sigma} = \bigcup\limits_{\Psi\in L\cup L^{\text{stop}}} {\Omega}^{V}_{\Psi} $$

Let us first prove the inclusion ${\Sigma }^{\triangleright } \subseteq {\Delta }_{1} \cup {\Delta }_{2}$ where

$${\Delta}_{1} = \{\mathcal{C}_{\mathbf{R}}\rightarrow B | B\subseteq \mathcal{C}_{\mathbf{R}^{L}}, \text{Hom}(\mathbf{R}, \boldsymbol{\Gamma}) \ne \emptyset\}$$

and

$$ {\Delta}_{2} = \{\mathcal{C}_{\mathbf{R}}\rightarrow B | B\subseteq \mathcal{C}^{\boldsymbol{\Gamma}}_{V}, \text{Hom}(\mathbf{R}, \boldsymbol{\Gamma})= \emptyset\}. $$

For this, it is enough to show that Δ₁ ∪Δ₂ is a full implicational system and ${\Sigma }\subseteq {\Delta }_{1} \cup {\Delta }_{2}$. The mapping ${\textsc O}: 2^{\mathcal {C}^{\boldsymbol {\Gamma }}_{V}}\rightarrow 2^{\mathcal {C}^{\boldsymbol {\Gamma }}_{V}}$, defined by ${\textsc O}(\mathcal {C}_{\mathbf {R}}) = \mathcal {C}_{\mathbf {R}^{L}}$ if Hom(R,Γ)≠∅ and ${\textsc O}(\mathcal {C}_{\mathbf {R}}) = \mathcal {C}^{\boldsymbol {\Gamma }}_{V}$ if Hom(R,Γ) = ∅, is the closure operator by its construction. Therefore, Theorem 5 implies that the set Δ₁ ∪Δ₂ is a full implicational system. The fact ${\Sigma }\subseteq {\Delta }_{1} \cup {\Delta }_{2}$ is obvious, because for any rule of the form (3), there exists an instance R such that $\mathcal {C}_{\mathbf {R}} = \{ \langle (v_{o_{t1}}, v_{o_{t2}}, ..., v_{o_{tn_{j_{t}}}}), {\varrho }_{j_{t}}\rangle | t\in [N] \}$. The naive evaluation algorithm (2) will put the tuple $(v_{1}, ..., v_{n_{u}})$ into r_u at the first iteration, because $(v_{1}, ..., v_{n_{u}})\in q_{u}(\mathbf {R})$. Thus, the head of that rule $\langle (v_{1}, ..., v_{n_{u}}), {\varrho }_{u}\rangle$ will be in $\mathcal {C}_{\mathbf {R}^{L}}$. Analogously, any rule of the form (4) is also in Δ₁ ∪Δ₂. Thus, we proved ${\Sigma }^{\triangleright } \subseteq {\Delta }_{1} \cup {\Delta }_{2}$, and next we need to prove ${\Delta }_{1} \cup {\Delta }_{2}\subseteq {\Sigma }^{\triangleright }$.

Note that the operator Q(R) operates on R = (V,r₁,...,r_s) by computing tuples from q_i(r₁,...,r_s),i ∈ [s] in the following way: computing $(v_{1}, ..., v_{n_{i}})\in q_{i}(r_{1}, ..., r_{s})$ can be modeled as a result of applying one of the rules (3) to attributes from $\mathcal {C}_{\mathbf {R}}$ to obtain the attribute $\langle (v_{1}, ..., v_{n_{i}}), {\varrho }_{i}\rangle$. Thus, $\mathcal {C}_{\mathbf {R}}\rightarrow \mathcal {C}_{Q(\mathbf {R})}\in {\Sigma }^{\triangleright }$. Therefore, $\mathcal {C}_{\mathbf {R}}\rightarrow \mathcal {C}_{Q^{l}(\mathbf {R})}\in {\Sigma }^{\triangleright }$ for any $l\in {\mathbb N}$, and we obtain $\mathcal {C}_{\mathbf {R}}\rightarrow \mathcal {C}_{\mathbf {R}^{L}}\in {\Sigma }^{\triangleright }$. Since Σ^⊳ is full, we conclude $\{\mathcal {C}_{\mathbf {R}}\rightarrow B | B\subseteq \mathcal {C}_{\mathbf {R}^{L}}\}\subseteq {\Sigma }^{\triangleright }$. Moreover, if Hom(R,Γ) = ∅, we can prove that any rule $\mathcal {C}_{\mathbf {R}}\rightarrow B, B\subseteq \mathcal {C}^{\boldsymbol {\Gamma }}_{V}$ is in Σ^⊳. This implies ${\Delta }_{1} \cup {\Delta }_{2}\subseteq {\Sigma }^{\triangleright }$.

In fact, we proved that the implicational system Σ corresponds to the closure operator ${\textsc O}:2^{\mathcal {C}^{\boldsymbol {\Gamma }}_{V}}\rightarrow 2^{\mathcal {C}^{\boldsymbol {\Gamma }}_{V}}$ (defined before) with respect to the canonical correspondence of Theorem 5. The closure operator O coincides with the densification operator Dense.

Thus, if Dense(Γ) can be solved by Datalog program L, then the implicational system Σ satisfies ${\Sigma }^{\triangleright } = {\Sigma }_{V}^{\boldsymbol {\Gamma }}$ and Γ is a DS-basis. □

Obviously, if Dense(Γ) can be solved by some Datalog program L ∪ L^stop, then all the more ¬CSP(Γ) can be expressed by Datalog. The following theorems give examples of constraint languages for which Dense(Γ) can be solved by Datalog.

Theorem 16

Let $\boldsymbol {\Gamma } = (D=\{0,1\}, \{(0)\}, \{(1)\}, {\varrho }_{x \wedge y\rightarrow z})$ where ${\varrho }_{x \wedge y\rightarrow z} = \{(a_{1}, a_{2}, a_{3})\in D^{3}| a_{1} a_{2}\leq a_{3}\}$. Then, there is a finite set of Horn formulas L over τ = {π₁,π₂,π₃}∪{F} such that Dense(Γ) can be solved by the Datalog program L.

Theorem 17

Let Γ = (D = {0,1},ϱ₁,ϱ₂,ϱ₃) where ϱ₁ = {(x,y)|x ∨ y}, ϱ₂ = {(x,y)|¬x ∨ y} and ϱ₃ = {(x,y)|¬x ∨¬y}. Then, there is a finite set of Horn formulas L over τ = {π₁,π₂,π₃}∪{F} such that Dense(Γ) can be solved by the Datalog program L.

Proof of Theorem 16 is given in Section 15 and proof of Theorem 17 is given in Section 16.

11 Classification of Dense(Γ) for the Boolean case

The problem Dense(Γ) is tightly connected with the so-called implication and equivalence problems, parameterized by Γ.

Definition 17

Let Γ = (D,ϱ₁,...,ϱ_s). The implication problem, denoted Impl(Γ), is a decision task with:

• An instance: two relational structures R = (V,r₁,...,r_s) and $\mathbf {R}^{\prime } = (V,r^{\prime }_{1}, ..., r^{\prime }_{s})$.

• An output: yes, if $\text {Hom}(\mathbf {R}, \boldsymbol {\Gamma }) \subseteq \text {Hom}(\mathbf {R}^{\prime }, \boldsymbol {\Gamma })$, and no, if otherwise.

Theorem 6.5 from [44] (which is based on the earlier result [45]) gives a complete classification of the computational complexity of Impl(Γ) for Boolean languages.

Theorem 18 (Schnoor, Schnoor, 2008)

If Γ is Schaefer, then Impl(Γ) can be solved in polynomial time. Otherwise, it is coNP-complete under logspace reductions.

This theorem directly leads us to the classification of Dense(Γ).

Theorem 19

If Γ is Schaefer, then Dense(Γ) is polynomially solvable. Otherwise, it is NP-hard.

Proof

Let us show that Dense(Γ) can be solved in polynomial time using an oracle access to Impl(Γ). Indeed, let R = (V,r₁,...,r_s) be an instance of Dense(Γ). Then, $\langle (v_{1},\cdots , v_{d}), {\varrho } \rangle \in \mathcal {C}_{V}^{\boldsymbol {\Gamma }}$ is in $\text {Dense}(\mathcal {C}_{\mathbf {R}})$ if and only if $\text {Hom}(\mathbf {R}, \boldsymbol {\Gamma }) \subseteq \text {Hom}(\mathbf {R}^{\prime }, \boldsymbol {\Gamma })$ where $\mathcal {C}_{\mathbf {R}^{\prime }} = \{\langle (v_{1},\cdots , v_{d}), {\varrho } \rangle \}$. Thus, by giving $(\mathbf {R},\mathbf {R}^{\prime })$ to an oracle of Impl(Γ), we decide whether $\langle (v_{1},\cdots , v_{d}), {\varrho } \rangle \in \text {Dense}(\mathcal {C}_{\mathbf {R}})$. By doing this for all $\langle (v_{1},\cdots , v_{d}), {\varrho } \rangle \in \mathcal {C}_{V}^{\boldsymbol {\Gamma }}$, we compute the whole set $\text {Dense}(\mathcal {C}_{\mathbf {R}})$ in polynomial time.

Thus, Dense(Γ) is polynomial time Turing reducible to Impl(Γ), and therefore, using Theorem 18, is polynomially solvable if Γ is Schaefer.

Let us now show that ¬Impl(Γ) is polynomial time Turing reducible to Dense(Γ). Given an instance $(\mathbf {R}, \mathbf {R}^{\prime })$ of ¬Impl(Γ), the inclusion $\text {Hom}(\mathbf {R}, \boldsymbol {\Gamma }) \subseteq \text {Hom}(\mathbf {R}^{\prime }, \boldsymbol {\Gamma })$ holds if and only if $\mathcal {C}_{\mathbf {R}^{\prime }}\subseteq \text {Dense}(\mathcal {C}_{\mathbf {R}})$. Thus, by computing $\text {Dense}(\mathcal {C}_{\mathbf {R}})$ one can efficiently decide whether $\mathcal {C}_{\mathbf {R}^{\prime }}\subseteq \text {Dense}(\mathcal {C}_{\mathbf {R}})$, i.e. whether $\text {Hom}(\mathbf {R}, \boldsymbol {\Gamma }) \subseteq \text {Hom}(\mathbf {R}^{\prime }, \boldsymbol {\Gamma })$. If $\mathcal {C}_{\mathbf {R}^{\prime }}\not \subseteq \text {Dense}(\mathcal {C}_{\mathbf {R}})$, our reduction outputs “yes”, and it outputs “no”, if otherwise.

If Γ is not Schaefer, then ¬Impl(Γ) is NP-complete, and therefore, Dense(Γ) is NP-hard. □

12 Non-Schaefer languages and mP/poly

For our proof of Theorem 6, we need to show Dense(Γ)∉mP/poly for non-Schaefer languages. Note that under $\text {NP}\not \subseteq \text {P/poly}$ (which is widely believed to be true), any NP-hard problem is outside of P/poly. Therefore, if Γ is not Schaefer, then Dense(Γ)∉P/poly (and all the more, Dense(Γ)∉mP/poly). In the current section we prove Dense(Γ)∉mP/poly unconditionally and this fact will be used in Section 13.

Theorem 20

Let Γ be a non-Schaefer language. Then, Dense(Γ)∉mP/poly.

Lemma 2

For any language Γ that is not constant preserving, if Dense(Γ) ∈mP/poly, then ¬CSP(Γ) ∈mP/poly.

Proof

Let R be an instance of CSP(Γ) and $\{x_{v}\}_{v\in \mathcal {C}_{V}^{\boldsymbol {\Gamma }}}$ be input boolean variables of a monotone polynomial-size circuit that computes $\text {Dense}(\mathcal {C}_{\mathbf R})$ such that x_v = 1 if and only if $v\in \mathcal {C}_{\mathbf R}$. Let $\{y_{v}\}_{v\in \mathcal {C}_{V}^{\boldsymbol {\Gamma }}}$ be output variables of that circuit, and y_v = 1 indicates $v\in \text {Dense}(\mathcal {C}_{\mathbf R})$. Then, $\bigwedge \limits _{v\in \mathcal {C}_{V}^{\boldsymbol {\Gamma }}}y_{v}=1$ if and only if Hom(R,Γ) = ∅. Thus, emptiness of Hom(R,Γ) can be decided by a polynomial-size monotone circuit. Therefore, ¬CSP(Γ) ∈mP/poly. □

In the case $D = \left \{ {0,1} \right \}$, there is a countable number of clones: in the list below we use the notation from the table on page 76 of [58] (the same results can be found in the table on page 1402 of [59]), together with the notation from the Table 1 of [60]. For every row, listed relations form a basis of the relational co-clone corresponding to the functional clone (notations of clones are given according to [58] and [60]). At the same time, the functional clone equals the set of polymorphisms of the relations. Below we list all Post co-clones Γ except for those that: a) satisfy {(0)},{(1)}∈Γ and b) Γ is Schaefer (and we are not interested in such languages in the current section).

(6)

Next, we will concentrate on languages listed in Table 6.

Our first goal is to study the complexity of Dense(Γ) where Γ = ({0,1},ϱ_b) where ϱ_b = {(x₂,x₁,x₃)|x₁ = x₂ ∨ x₁ = x₃}.

Lemma 3

Dense(Γ = ({0,1},ϱ_b))∉mP/poly.

Proof

Let us introduce the restriction of CSP(Γ), Γ = ({0,1},ϱ_b,{(0)},{(1)}), in which we assume that in its instance R = (V,r,{Z},{O}) the domain V contains two designated variables, Z and O, with unary constraints, Z = 0 and O = 1. This task is denoted by CSP_b.

It is easy to see that

$$ \begin{array}{llllll} {\varrho}_{\text{NAE}}(x,y,z) = \exists t, O, Z {\varrho}_{\mathrm{b}}(x,t,z) \wedge {\varrho}_{\mathrm{b}}(t,Z,y) \wedge {\varrho}_{\mathrm{b}}(t,O,y) \wedge [O=1] \wedge [Z=0] \end{array} $$

where ϱ_NAE = {(x₁,x₂,x₃)|x₁≠x₂ ∨ x₁≠x₃}. Thus, by CSP_b we can model any instance of CSP({ϱ_NAE}). The standard reduction of CSP({ϱ_NAE}) to CSP_b can be implemented as a monotone circuit. Since {ϱ_NAE,{(0)},{(1)}} is not of bounded width and ¬CSP({ϱ_NAE}) is equivalent to ¬CSP({ϱ_NAE,{(0)},{(1)}}) modulo polynomial-size reductions by monotone circuits (see analogous argument in the proof of Corollary 1), we conclude ¬CSP({ϱ_NAE})∉mP/poly (using Proposition 5.1. from [48]). Therefore, ¬CSP_b∉mP/poly.

Let us now prove that Dense(Γ), where Γ = ({0,1},ϱ_b), is outside of mP/poly. Let R = (V,r) be an instance of Dense(Γ = ({0,1},ϱ_b)) and let ${\mathbf R}^{\prime } =(V, r)$ be such that $r^{\prime }\supseteq r$ and $({\mathbf R}^{\prime }, \boldsymbol {\Gamma })$ is a maximal instance. By construction, for any i,j ∈ V, $(i,j,i)\in r^{\prime }$ if and only if there is no such h ∈Hom(R,Γ) that satisfies h(i) = 0 and h(j) = 1. But the last question, i.e. checking the emptiness of {h ∈Hom(R,Γ)|h(i) = 0,h(j) = 1} is equivalent to ¬CSP_b after setting Z = i,O = j. The latter argument can be turned into a reduction of ¬CSP_b to Dense(Γ = ({0,1},ϱ_b)). Again, this reduction can be implemented as a monotone circuit.

Therefore, Dense(Γ = ({0,1},ϱ_b))∉mP/poly. □

Lemma 4

If 〈Γ〉 equals one of inv(U₀),inv(U₁),inv(SU),inv(MU) and inv(U), then ϱ_b is strongly reducible to Γ.

Proof

Let Γ = {ρ₁,⋯ ,ρ_s}. Since ${\varrho }_{\mathrm {b}}\in \text {inv}(U)\subseteq \text {inv} (U_{0}), \text {inv} (U_{1}), \text {inv} (SU), \text {inv} (M U)$, then ${\varrho }_{\mathrm {b}} = {\Psi }^{\boldsymbol {\Gamma }}$ for a primitive positive formula Ψ over τ = {π₁,⋯ ,π_s}. Let

$${\Psi} = \exists x_{4}... x_{l} \bigwedge\limits_{t\in [N]}\pi_{j_{t}} (x_{o_{t1}}, x_{o_{t2}}, ...).$$

Let us denote ${\Phi } = \bigwedge _{t\in [N]}\pi _{j_{t}} (x_{o_{t1}}, x_{o_{t2}}, ...)$ and consider a relation $\gamma =\{{\mathbf x}\in \{0,1\}^{l}\mid {\mathbf x}\in {\Phi }^{\boldsymbol {\Gamma }} \text {or} {\mathbf x}_{1:3}\notin {\varrho }_{\mathrm {b}}\}$. Let us prove that if u ∈pol(Φ^Γ) and u is unary, then u ∈Pol(Γ). The latter can be checked by considering all 4 cases: u(x) = x, or ¬x, or 0, or 1. A unary u(x) = x is a polymorphism of any relation. If u(x) = c, then u ∈pol(Φ^Γ) means that Φ^Γ is a c-preserving relation. Then γ is also c-preserving. Finally, if u(x) = ¬x, then u ∈pol(Φ^Γ) means that Φ^Γ is a self-dual relation. Therefore, γ = Φ^Γ ∪{(0,1,0),(1,0,1)}× D^l− 3 is also self-dual, i.e. u ∈Pol(Γ).

From the last fact we conclude that $\{u: D\to D \mid u\in \text {Pol}({\Gamma })\}\subseteq \{u: D\to D \mid u\in \text {pol}(\{\gamma \})\}$. Since {u : D → D∣u ∈Pol(Γ)} forms a basis of Pol(Γ) (in all listed cases), then γ ∈inv(Pol(Γ)), i.e. γ ∈〈Γ〉.

Finally, by construction we have γ = Φ^Γ ∪ δ where $\text {pr}_{1,2,3}\delta = D^{3}\setminus {\varrho }_{\mathrm {b}}$ and $\text {pr}_{1,2,3} {\Phi }^{\boldsymbol {\Gamma }}={\varrho }_{\mathrm {b}}$. This is exactly the needed condition for ϱ_b to be strongly reducible to Γ. □

Proof Proof of Theorem 20

We have D = {0,1}. Our goal is to prove that if Γ is non-Schaefer then Dense(Γ) is outside of mP/poly.

Let us first consider the subcase where CSP(Γ) is NP-hard. Then, by construction, Γ is not constant preserving and core(Γ) = Γ. Therefore, ¬CSP(Γ) and ¬CSP(Γ ∪{(0)}∪{(1)}) can be mutually reduced by polynomial-size monotone circuits (as in the proof of corollary 1). Since ¬CSP(Γ) ≡¬CSP(Γ ∪{(0)}∪{(1)})∉mP/poly (by proposition 5.1. from [48]), then, by Lemma 2, Dense(Γ)∉mP/poly.

Next, let us consider the subcase where CSP(Γ) is tractable. Since we already assumed that Γ is not any of 4 Schaeffer classes, this can happen only if Γ is constant preserving. Therefore, $\{\{0\}, \{1\}\}\not \subseteq \langle {\Gamma }\rangle$. All possible variants for Pol(Γ) are listed in Table 6. Since $\langle \{{\varrho }_{\mathrm {b}}\}\rangle = \text {inv}(U)\subseteq \text {inv} (U_{0}), \text {inv} (U_{1}), \text {inv} (SU), \text {inv} (M U)$, Lemma 3 in combination with Lemma 4 and part (c) of Theorem 11 gives us that Dense(Γ)∉mP/poly. □

13 Proof of Theorem 6

Let us prove first that for the Boolean domain D = {0,1}, if Γ satisfies one of the following 3 conditions

• (a) Γ is a subset of 〈{ϱ₁,ϱ₂,ϱ₃}〉 where ${\varrho }_{1} = \left \{{\left ({x, y} \right ) | x \vee y} \right \}$, ${\varrho }_{2} = \left \{{\left ({x, y} \right ) | \neg x \vee y} \right \}$ and ${\varrho }_{3} = \left \{{\left ({x, y} \right ) | \neg x \vee \neg y} \right \}$ (2-SAT);

• (b) Γ is a subset of $\langle \{\{(0)\}, \{(1)\}, {\varrho }_{x \wedge y\rightarrow z}\}\rangle$ (Horn case);

• (c) Γ is a subset of $\langle \{\{(0)\}, \{(1)\}, {\varrho }_{\neg x \wedge \neg y\rightarrow \neg z}\}\rangle$ (dual-Horn case).

then it has a weak polynomial densification operator.

Note that from Theorems 9 and 10 it follows that in all three cases Γ is a subset of the relational clone of an A-language. Part (b) of Theorem 11 claims that Γ has a weak polynomial densification operator if languages $\{{\varrho }_{1}, {\varrho }_{2}, {\varrho }_{3}\}, \{\{(0)\}, \{(1)\}, {\varrho }_{x \wedge y\rightarrow z}\}$ have one. Theorems 15, 16 and 17 give us that $(D,{\varrho }_{1}, {\varrho }_{2}, {\varrho }_{3}), (D,\{(0)\}, \{(1)\}, {\varrho }_{x \wedge y\rightarrow z})$ are DS-templates. Therefore, Γ has a weak polynomial densification operator.

It remains to prove that, in the Boolean case, the weak polynomial densification property implies one of these 3 conditions.

For the general domain D, if a constraint language Γ has a weak polynomial densification operator, then its core is of bounded width (Theorem 8). Thus, in the Boolean case, if Γ is not constant-preserving and has a weak polynomial densification operator, then it is of bounded width (i.e. Γ is in one of the latter three classes). If Γ preserves some constant c, then w.l.o.g. we can assume that c = 0. From Theorem 4, whose proof is given in Section 11, it is clear that either a) Dense(Γ) is NP-hard, or b) Γ is Schaefer, i.e. {{0},{1}}∪Γ is tractable. In the first case, existence of a polynomial-size implicational system for the densification operator implies that there exists a monotone circuit of size poly(|V |) that computes the densification operator Dense (a construction of such a circuit is identical to the one given in Theorem 8). In other words, Dense(Γ) ∈mP/poly. This contradicts to the claim of Theorem 20 that Dense(Γ)∉mP/poly for non-Schaefer languages.

Thus, we have option b), and this can happen only if either b.1) Γ preserves ∨, or ∧, or mjy(x,y,z) = (x ∧ y) ∨ (x ∧ z) ∨ (y ∧ z), or b.2) Γ preserves x ⊕ y ⊕ z, but does not preserve ∨,∧ and mjy. In the first case, Γ satisfies the needed conditions. In the second case, Γ is a 0-preserving language, i.e. 0,x ⊕ y ⊕ z ∈Pol(Γ), but ∨,∧,mjy∉Pol(Γ). According to Table 2.1 on page 76 of Marchenkov’s textbook [58], there are only two functional clones with these properties, i.e. either b.2.1) Pol(Γ) = L where L = {a₀ ⊕ a₁x₁ ⊕⋯ ⊕ a_kx_k} is a set of all linear functions, or b.2.2) Pol(Γ) = L₀ where L₀ = {a₁x₁ ⊕⋯ ⊕ a_kx_k}. In both cases ρ_L = {(x,y,z,t)∣x ⊕ y ⊕ z ⊕ t = 0}∈〈Γ〉.

Lemma 5

If Pol(Γ) = L₀ or Pol(Γ) = L, then ρ_L is strongly reducible to Γ.

Proof

Note that $x\oplus y\in L_{0}\subseteq L$. Therefore, for any ϱ ∈〈Γ〉 we have ∀x,y ∈ ϱ →x ⊕y ∈ ϱ where ⊕ is applied component-wise, i.e. ϱ is a linear subspace. Since ρ_L ∈〈Γ〉, then there is a quantifier-free primitive positive formula Φ(x₁,⋯ ,x_l) such that $\rho _{L} = \text {pr}_{1,2,3,4}{\Phi }^{\boldsymbol {\Gamma }}$. Let us set Ψ(x₁,⋯ ,x_l) = ∃x₄Φ(x₁,⋯ ,x_l), i.e. Ψ depends on x₄ fictitiously. Let us define δ = Ψ^Γ ∖Φ^Γ. Thus, we have Φ^Γ ∪ δ ∈〈Γ〉, $\rho _{L} = \text {pr}_{1,2,3,4}{\Phi }^{\boldsymbol {\Gamma }}$ and $\text {pr}_{1,2,3,4}\delta =\text {pr}_{1,2,3,4} {\Psi }^{\boldsymbol {\Gamma }}\setminus {\Phi }^{\boldsymbol {\Gamma }} = \text {pr}_{1,2,3,4} \{{\mathbf x}\oplus a(0,0,0,1,0,\cdots ,0)\mid a\in D, {\mathbf x}\in {\Phi }^{\boldsymbol {\Gamma }}\}\setminus {\Phi }^{\boldsymbol {\Gamma }} = \text {pr}_{1,2,3,4} \{{\mathbf x}\oplus (0,0,0,1,0,\cdots ,0)\mid {\mathbf x}\in {\Phi }^{\boldsymbol {\Gamma }}\}= \{(x,y,z,t)\mid x\oplus y\oplus z \oplus t=1\} = D^{4}\setminus \rho _{L}$. The latter is the condition for strong reducibility of ρ_L to Γ. □

Using part (b) of Theorem 11, the weak polynomial densification property of Γ and the latter lemma, we obtain that {ρ_L} has a weak polynomial densification operator. The following Lemma contradicts to our conclusion. Therefore, in the Boolean case, the weak polynomial densification property implies one of 3 conditions given above.

Lemma 6

{ρ_L} does not have a weak polynomial densification operator.

Proof

Let us prove the statement by reductio ad absurdum. Suppose that Γ = {ρ_L} has a weak polynomial densification operator. Therefore, Dense(Γ) ∈mP/poly.

Since the core of ${\Gamma }^{\prime }=\{{\varrho }, \{(0)\}, \{(1)\}\}$ where ϱ = {(x,y,z)∣x ⊕ y ⊕ z = 0} is not of bounded width, by proposition 5.1 from [48], $\neg \text {CSP}(\boldsymbol {\Gamma }^{\prime })$ cannot be computed by a polynomial-size monotone circuit. Let us describe a monotone reduction of $\neg \text {CSP}(\boldsymbol {\Gamma }^{\prime })$ to Dense(Γ) which will imply $\neg \text {CSP}(\boldsymbol {\Gamma }^{\prime })\in \text {mP/poly}$. This will be a contradiction.

According to [58], Γ = {ρ_L} is a basis of Inv(L₀). Therefore, 〈{ρ_L}〉 equals the set of all linear subspaces in $\{0,1\}^{n}, n\in {\mathbb N}$. In other words, for any ([n],r), Hom(([n],r),Γ) is a linear subspace of {0,1}ⁿ, and $\{\text {pr}_{[k]}\text {Hom}(([n], r),\boldsymbol {\Gamma }) \mid n\in {\mathbb N}, k\leq n, r\subseteq [n]^{4}\}$ spans all possible linear subspaces.

Let $\mathbf {R}^{\prime } = ([n], r^{\prime }, Z, O)$ be an instance of $\neg \text {CSP}(\boldsymbol {\Gamma }^{\prime }=(D,{\varrho }, \{(0)\}, \{(1)\}))$. Since ϱ,{(0)}∈〈{ρ_L}〉, a set of constraints $\{\langle (v_{1},v_{2},v_{3}), {\varrho }\rangle \mid (v_{1},v_{2},v_{3})\in r^{\prime }\}\cup \{\langle v, \{(0)\}\rangle \mid v\in Z\}\cup \{\langle (n+1,n+2,n+3),{\varrho }\rangle \}$ can be modeled as a set of constraints over {ρ_L} with an extended set of variables [m],m ≥ n + 3, or alternatively, as an instance $\mathbf {R}^{\prime \prime } = ([m], r)$ of CSP({ρ_L}). Let $\sim$ be an equivalence relation on [m + 1] with equivalence classes {{i}∣i ∈ [m] ∖ O} ∪{{m + 1}∪ O} and let $\overline {x}$ denote an equivalence class that contains x ∈ [m + 1]. A relational structure $\mathbf {R} = ([m+1]/\sim , \overline {r})$ where $\overline {r} = \{(\overline {x}, \overline {y}, \overline {z}, \overline {t}) \mid (x,y,z,t)\in r\}$, considered as an instance of Dense({ρ_L}), satisfies: $(\overline {n+1},\overline {n+2},\overline {n+3},\overline {m+1})\in \text {Dense}(\mathcal {C}_{\mathbf {R}})$ if and only if $\text {Hom}(\mathbf {R}^{\prime }, \boldsymbol {\Gamma }^{\prime }) = \emptyset$. Indeed, the constraint 〈(n + 1,n + 2,n + 3),ϱ〉 that is satisfied for assignments in $\text {Hom}(\mathbf {R}^{\prime \prime }, \boldsymbol {\Gamma })$, together with $(\overline {n+1},\overline {n+2},\overline {n+3},\overline {m+1})\in \text {Dense}(\mathcal {C}_{\mathbf {R}})$, implies that $h(\overline {m+1})=0$ for any h ∈Hom(R,Γ). Or, equivalently, $\{h\in \text {Hom}(\mathbf {R}, \boldsymbol {\Gamma }) \mid h(\overline {m+1})=1\}=\emptyset$. The latter is equivalent to $\{h\in \text {Hom}(\mathbf {R}^{\prime \prime }, \boldsymbol {\Gamma }) \mid h(x)=1, x\in O\}=\emptyset$, or $\text {Hom}(\mathbf {R}^{\prime }, \boldsymbol {\Gamma }^{\prime })=\emptyset$.

By construction, the indicator Boolean vector of the subset $\mathcal {C}_{\mathbf {R}^{\prime \prime }}\in 2^{\mathcal {C}_{[m]}^{\boldsymbol {\Gamma }}}$, i.e. the Boolean vector $\mathbf {x}\in \{0,1\}^{\mathcal {C}_{[m]}^{\boldsymbol {\Gamma }}}$, $\mathbf {x}(\langle (v_{1}, v_{2},v_{3},v_{4}), \rho _{L}\rangle )=1\Leftrightarrow \langle (v_{1}, v_{2},v_{3},v_{4}), \rho _{L}\rangle \in \mathcal {C}_{\mathbf {R}^{\prime \prime }}$ can be computed from the indicator Boolean vector of $\mathcal {C}_{\mathbf {R}^{\prime }}\in 2^{\mathcal {C}_{[n]}^{\boldsymbol {\Gamma }^{\prime }}}$ by a polynomial-size monotone circuit. Further, the indicator Boolean vector of the subset $\mathcal {C}_{\mathbf {R}}\in 2^{\mathcal {C}_{[m+1]/\sim }^{\boldsymbol {\Gamma }}}$ can be computed by a polynomial-size monotone circuit from the indicator Boolean vector of $\mathcal {C}_{\mathbf {R}^{\prime \prime }}\in 2^{\mathcal {C}_{[m]}^{\boldsymbol {\Gamma }}}$ and the indicator Boolean vector of O ∈ 2^[n]. Finally, we feed the indicator vector of $\mathcal {C}_{\mathbf {R}}$ to Dense(Γ) and compute whether $(\overline {n+1},\overline {n+2},\overline {n+3},\overline {m+1})\in \text {Dense}(\mathcal {C}_{\mathbf {R}})$. Thus, the emptiness of $\text {Hom}(\mathbf {R}^{\prime }, \boldsymbol {\Gamma }^{\prime })$ can be decided by a polynomial-size monotone circuit which contradicts $\neg \text {CSP}({\Gamma }^{\prime })\not \in \text {mP/poly}$. □

14 Proofs of Theorems 9 and 10

Proof Proof of Theorem 9

Let Γ = (D = {0,1},ϱ₁,ϱ₂,ϱ₃) where ϱ₁ = {(x,y)|x ∨ y}, ϱ₂ = {(x,y)|¬x ∨ y} and ϱ₃ = {(x,y)|¬x ∨¬y}.

First, let us note that any binary relation $\rho \subseteq D^{2}$ is strongly reducible to Γ, due to $\rho = \bigcap _{\gamma \in S: \rho \subseteq \gamma }\gamma$ where $S = \{{\varrho }_{1},{\varrho }_{2},{\varrho }_{3}, {{\varrho }_{2}^{T}}\}$, ${{\varrho }_{2}^{T}} = \{(y,x)\mid (x,y)\in {\varrho }_{2}\}$ (in the definition of strong reducibility one can set ${\Xi }(x,y) = \bigwedge _{i:\rho \subseteq {\varrho }_{i}} \pi _{i}(x,y) \bigwedge _{\rho \subseteq {{\varrho }^{T}_{2}}} \pi _{2}(y,x)$ and δ = D² ∖ ρ).

It is well-known that 〈Γ〉 = pol(mjy) where mjy(x,y,z) = (x ∧ y) ∨ (x ∧ z) ∨ (y ∧ z) is a majority operation. Every n-ary relation ρ ∈〈Γ〉 is defined by its binary projections ρ_ij = {(x_i,x_j)∣(x₁,⋯ ,x_n) ∈ ρ}, i.e.

$$ \rho = \bigcap\limits_{i,j \in [n]}r_{ij} $$

where r_ij = {(x₁,⋯ ,x_n)∣(x_i,x_j) ∈ ρ_ij}. Since ρ_ij is strongly reducible to Γ, r_ij also has this property. Thus, ρ is A-reducible to Γ, and therefore, Γ is an A-language. □

The Horn case

Let $\boldsymbol {\Gamma } = (D=\{0,1\}, \{(0)\}, \{(1)\}, {\varrho }_{x \wedge y\rightarrow z})$. In other words, 〈Γ〉 is a set of relations that is closed under component-wise conjunction, i.e. x,y ∈ ρ ∈〈Γ〉 implies x ∧y ∈ ρ.

Lemma 7

Let D = {0,1} and ρ be a set of satisfying assignments of a Horn clause, i.e.

$$\rho = \{(x_{1}, \cdots, x_{n})\mid (x_{1}\wedge \cdots\wedge x_{n}\to 0)\}$$

or

$$\rho = \{(x_{1}, \cdots, x_{n+1})\mid (x_{1}\wedge \cdots\wedge x_{n}\to x_{n+1})\}.$$

Then, ρ is strongly reducible to Γ.

Proof

Let us consider first the case of Φ = (x₁ ∧⋯ ∧ x_n → 0). This formula can be given as Φ ≡∃x_n+ 1,⋯ ,x_2n− 1Ξ(x₁,⋯ ,x_2n− 1) where

$$ {\Xi}(x_{1}, \cdots,x_{2n-1}) =(x_{1}\wedge x_{2}\to x_{n+1}) \wedge (x_{2n-1}=0) \bigwedge\limits_{i=3}^{n} (x_{i}\wedge x_{n+i-2}\to x_{n+i-1}). $$

If we define a 2n − 1-ary δ as {(1,⋯ ,1)}, then it can be checked that Ξ^Γ ∪ δ is a ∧-closed set. Indeed, for any x ∈Ξ^Γ and y ∈ δ, we have x ∧y = x ∈Ξ^Γ∪ δ. Since both Ξ^Γ and δ are ∧-closed, then we conclude the statement. Therefore, Ξ^Γ ∪ δ ∈〈Γ〉. It remains to check that $\text {pr}_{1:n}{\Xi }^{\boldsymbol {\Gamma }} = \rho$ and $\text {pr}_{1:n}\delta = \{0,1\}^{n}\setminus \rho$. Thus, Ξ^Γ ∪ δ ∈〈Γ〉 and ρ = {(x₁,⋯ ,x_n)∣(x₁ ∧⋯ ∧ x_n → 0)} is strongly reducible to Γ.

Let us now consider the case of Φ = (x₁ ∧⋯ ∧ x_n → x_n+ 1). Let us denote by (x ∧ y = z) the formula (x ∧ y → z) ∧ (z ∧ O → x) ∧ (z ∧ O → y) ∧ (O = 1) where O is an additional fixed variable. Note that (x ∧ y = z) is a quantifier-free primitive positive formula over τ. Thus, we have Φ ≡∃x_n+ 2,⋯ ,x_2n− 1,OΞ(x₁,⋯ ,x_2n− 1,O) where

$$ \begin{array}{llllll} {\Xi}(x_{1}, \cdots,x_{2n-1},O) = (x_{1}\!\wedge\! x_{2} = x_{n+2}) \!\wedge \!(x_{n}\!\wedge\! x_{2n-1}\!\to\! x_{n+1}) \!\wedge \bigwedge\limits_{i=3}^{n-1} (x_{i}\wedge x_{n+i-1} = x_{n+i}). \end{array} $$

Here we define a 2n-ary δ as {1}ⁿ ×{0}×{1}^n− 1. Let us prove that Ξ^Γ ∪ δ is a ∧-closed set. Again, let us consider x ∈Ξ^Γ and y ∈ δ. If x_n+ 1 = 0, then x ∧y = x ∈Ξ^Γ∪ δ. Otherwise, if x_n+ 1 = 1, we have either a) x = 1^2n− 1 and in that case 1^2n− 1 ∧y = y ∈Ξ^Γ∪ δ, or b) at least one of x₁,⋯ ,x_n is 0. In the case of b) let i ∈ [n] be the smallest such that x_i = 0, i.e. x_j = 1,j ∈ [i − 1]. Therefore, x_n+j = 1,j ∈ [2,i − 1] and x_n+j = 0,j ∈ [i,n − 1]. It remains to check that an assignment x ∧y = (x₁,⋯ ,x_n,0,x_n+ 2,⋯ ,x_2n− 1) also satisfies Ξ, and therefore, is in Ξ^Γ ∪ δ. Thus, Ξ^Γ ∪ δ ∈〈Γ〉 and ρ is strongly reducible to Γ. □

Proof Proof of Theorem 10

Let ρ ∈〈Γ〉 be n-ary, i.e. ρ is closed with respect to component-wise conjunction. A classical result about ∧-closed relations (see [61, 62]) states that ρ can be represented as:

$$ \rho = \bigcap\limits_{i=1}^{l} \rho_{i} $$

where $\rho _{i} = \{(x_{1}, \cdots , x_{n}) \mid {\Phi }_{i}(x_{s_{i1}}, \cdots , x_{s_{i r_{i}}})\}$ where Φ_i is a Horn clause. From the previous Lemma we conclude that each of ρ_i,i ∈ [l] is strongly reducible to Γ. Therefore, ρ is A-reducible to Γ. Since this is true for any ρ ∈〈Γ〉, we conclude that Γ is an A-language. □

15 Proof of Theorem 16

In this case we have a vocabulary τ = {π₁,π₂,π₃} where π₁,π₂ are unary and π₃ is assigned an arity 3.

Let R = (V,Z,O,r) be an instance of Dense(Γ). Let us define an implicational system Σ on V that consists of rules $\{i,j\}\rightarrow k$ for any (i,j,k) ∈ r. The implicational system Σ defines a closure operator $o_{\Sigma }(S) = \{x| (S\rightarrow x)\in {\Sigma }^{\triangleright }\}$. Let ${\mathbf R}^{\prime } = (V, Z^{\prime }, O^{\prime }, r^{\prime })$ be a maximal instance such that $Z^{\prime }\supseteq Z$, $O^{\prime }\supseteq O$, $r^{\prime }\supseteq r$ and $\text {Hom} ({\mathbf R}, \boldsymbol {\Gamma })=\text {Hom} ({\mathbf R}^{\prime }, \boldsymbol {\Gamma })\ne \emptyset$. Note that $(i,j,k)\in r^{\prime }$ if and only if k ∈ o_Σ({i,j}∪ O) and Z ∩ o_Σ({i,j}∪ O) = ∅. Indeed, for any k ∈ o_Σ({i,j}∪ O) we have $(i,j,k)\in r^{\prime }$, because $\{i,j\}\cup O\rightarrow k$ is a consequence of rules in r. On the contrary, let k∉o_Σ({i,j}∪ O). Then, h : V → D defined by h(v) = 1 if v ∈ o_Σ({i,j}∪ O) and h(v) = 0, if otherwise, is a homomorphism from R to Γ. Therefore, for any k∉o_Σ({i,j}∪ O) we have (h(i),h(j),h(k))∉ϱ₃. Using Theorem 2, we obtain $(i,j,k)\notin r^{\prime }$.

Thus, for any $(i,j,k)\in r^{\prime }$ there exists a derivation of k from {i,j}∪ O using only rules $\{i,j\}\rightarrow k$, (i,j,k) ∈ r. To such a derivation one can always correspond a rooted binary tree T whose nodes are labeled with elements of V, the root is labeled with k, and all leaves are labeled by elements of {i,j}∪ O. Any (non-leaf) node p (a parent) of the tree T has two children c₁,c₂ such that $\{l(c_{1}), l(c_{2})\}\rightarrow l(p)$ is in Σ (l is a labeling function).

Let x,y be two leaves of the tree T with a common parent z such that the distance from x to the root k equals the depth of the tree (i.e. is the largest possible one). The parent of z is denoted by u and all possible branches under u are drawn in Fig. 1: we reduced the number of possible branches to analyze using the rule π₃(x,y,u) → π₃(y,x,u) that makes an order of children irrelevant. Circled leaves correspond to leaves labeled by elements of O. A leaf that is not circled can be labeled either by i,j or by an element from O. For each case, the Figure shows how to reduce the tree T by deleting redundant nodes under u. To delete the redundant nodes and connect leaves to u we have to verify that a new reduced branch with a parent u and 2 leaves x,y (or, x,t) corresponds to a triple (x,y,u) ∈ r^L (or, (x,t,u) ∈ r^L), i.e. the resulting triple can be obtained using rules from L. Needed rules are indicated near each deletion operation in Fig. 1.

Fig. 1

A new reduced branch with a parent u and 2 leaves x,y (or, x,t) corresponds to a triple (x,y,u) ∈ r^L. There is no need to list cases with 3 nodes labeled by O, because they all are subcases of the listed

It is easy to see that using such deletions we will eventually obtain a root k with two children labeled by c₁,c₂ ∈{i,j}∪ O. Therefore, the triple (c₁,c₂,k) is in r^L. If {c₁,c₂} = {i,j}, then (i,j,k) can be obtained from (c₁,c₂,k) using the rule (1) from the list below. If c₁ = i and c₂ ∈ O (or, c₁,c₂ ∈ O), then (i,j,k) can be obtained from (c₁,c₂,k) using the rule (2). Thus, (i,j,k) ∈ r^L, i.e. we proved that $r^{\prime } = r^{L}$.

Let us show now that $O^{\prime }=O^{L}$. Analogously to the previous analysis, k ∈ o_Σ(O) if there is a derivation tree with a root k labeled with elements of V and all leaves are labeled by elements of O. Using the same reduction we finally obtain the triple (i,j,k) ∈ r^L, where i,j ∈ O. Using the rule (3), we conclude k ∈ O^L, i.e. we proved the inclusion $O^{L} \supseteq o_{\Sigma }(O)$. Therefore, O^L = o_Σ(O). Then, h : V → D defined by h(v) = 1 if v ∈ o_Σ(O) and h(v) = 0, if otherwise, is a homomorphism from R to Γ. Since for any v∉O^L we have h(v)∉ϱ₂, then using Theorem 2, we obtain that o_Σ(O) = O^L is maximal and $O^{\prime }=O^{L}$.

Finally, let us prove that $Z^{\prime }=Z^{L}$. First, let us prove $Z^{\prime } = \{v\in V| o_{\Sigma } (\{v\}\cup O)\cap Z \ne \emptyset \}$. Indeed, if a ∈ V is such that o_Σ({a}∪ O) ∩ Z≠∅, then the set {h ∈Hom(R,Γ)|h(a) = 1} is empty. Therefore, h(a) = 0 for any h ∈Hom(R,Γ), which implies $a\in Z^{\prime }$. On the contrary, if a ∈ V is such that o_Σ({a}∪ O) ∩ Z = ∅, then h : V → D defined by h(v) = 1 if v ∈ o_Σ({a}∪ O) and h(v) = 0, if otherwise, is a homomorphism from R to Γ. Therefore, $a\notin Z^{\prime }$.

Thus, $Z^{\prime }$ is a set of all elements a ∈ V such that some element r ∈ Z can be derived from {a}∪ O in the implicational system Σ. Analogously to the previous case, there is a rooted binary tree T with a root r ∈ Z whose nodes are labeled by elements of V and leaves are labeled by {a}∪ O. Using the same technique this tree can be reduced to a root r with two children c₁ and c₂, such that $\{c_{1}, c_{2}\}\subseteq \{a\} \cup O$, $\{c_{1}, c_{2}\}\not \subseteq O$ and (c₁,c₂,r) ∈ r^L. W.l.o.g. let c₁ = a. If c₂ ∈ O, then using the rule (4) we can deduce a ∈ Z^L. If c₂ = a, then using the rule (5) we can deduce a ∈ Z^L. Thus, $Z^{\prime }\subseteq Z^{L}$, and consequently, $Z^{\prime }= Z^{L}$.

In the case Hom(R,Γ) = ∅, it is easy to see that we will eventually apply the rule (6).

The complete list of Horn formulas in L is given below:

• (1) $\forall x,y,u \big (\pi _{3} (x, y, u) \rightarrow \pi _{3} (y, x, u)\big )$

• (2) $\forall x,y,z,u \big (\pi _{3} (x, y, u)\wedge \pi _{2} (x) \rightarrow \pi _{3} (z, y, u)\big )$

• (3) $\forall x,y,z,u \big (\pi _{3} (x, y, u)\wedge \pi _{2} (x)\wedge \pi _{2} (y) \rightarrow \pi _{2} (u)\big )$

• (4) $\forall x,y,z,u \big (\pi _{3} (x, y, u)\wedge \pi _{2} (x) \wedge \pi _{1} (u) \rightarrow \pi _{1} (y)\big )$

• (5) $\forall x,y \big (\pi _{3} (x, x, y)\wedge \pi _{1} (y) \rightarrow \pi _{1} (x)\big )$

• (6) $\forall x \big (\pi _{1} (x)\wedge \pi _{2} (x) \rightarrow \mathrm {F}\big )$

• (7) $\forall x,y,z,u \big (\pi _{3} (x, y, z) \wedge \pi _{3} (z, x, u) \rightarrow \pi _{3} (x, y, u)\big )$

• (8) $\forall x,y,z,t,u \big (\pi _{3} (x, y, z) \wedge \pi _{3} (x, x, t) \wedge \pi _{3} (z, t, u) \rightarrow \pi _{3} (x, y, u)\big )$

• (9) $\forall x,y,z,t,u \big (\pi _{3} (x, y, z) \wedge \pi _{3} (x, y, t) \wedge \pi _{3} (z, t, u) \rightarrow \pi _{3} (x, y, u)\big )$

• (10) $\forall x,y,z,t,u \big (\pi _{3} (x, y, z)\wedge \pi _{3} (z, t, u)\wedge \pi _{2}(t) \rightarrow \pi _{3}(x,t,u)\big )$

• (11) $\forall x,y,z,t,u \big (\pi _{3} (x, y, z)\wedge \pi _{3} (z, t, u)\wedge \pi _{2}(y) \rightarrow \pi _{3}(x,y,u)\big )$

• (12) $\forall x,y,y^{\prime },z,t,u \big (\pi _{3} (x, y, z)\wedge \pi _{3} (z, t, u)\wedge \pi _{3} (x, y^{\prime }, t)\wedge \pi _{2}(y^{\prime }) \rightarrow \pi _{3}(x,y,u)\big )$

• (13) $\forall x,y,y^{\prime },z,t,u \big (\pi _{3} (x, x, z)\wedge \pi _{3} (z, t, u)\wedge \pi _{3} (y, y^{\prime }, t)\wedge \pi _{2}(y^{\prime }) \rightarrow \pi _{3}(x,y,u)\big )$

• (14) $\forall x,y,z,t,u \big (\pi _{3} (x, y, z)\wedge \pi _{3} (z, t, u)\wedge \pi _{2} (y)\wedge \pi _{2}(t) \rightarrow \pi _{3}(x,y,u)\big )$

• (15) $\forall x,y,x^{\prime },y^{\prime },z,t,u \big (\pi _{3} (x, y, z)\wedge \pi _{3} (z, t, u)\wedge \pi _{3} (x^{\prime }, y^{\prime }, t)\wedge \pi _{2} (x^{\prime })\wedge \pi _{2}(y^{\prime }) \rightarrow \pi _{3}(x,y,u)\big )$

• (16) $\forall x,y,x^{\prime },y^{\prime },z,t,u \big (\pi _{3} (x, y, z)\wedge \pi _{3} (z, t, u)\wedge \pi _{3} (x^{\prime }, y^{\prime }, t)\wedge \pi _{2} (y)\wedge \pi _{2}(y^{\prime }) \rightarrow \pi _{3}(x,x^{\prime },u)\big )$

This list is not optimized and some formulas could be derivable from others.

16 Proof of Theorem 17

Throughout the proof we assume D = {0,1} and Γ = (D,ϱ₁,ϱ₂,ϱ₃) where ϱ₁ = {(x,y)|x ∨ y}, ϱ₂ = {(x,y)|¬x ∨ y} and ϱ₃ = {(x,y)|¬x ∨¬y}. For $\rho _{1}, \rho _{2}\subseteq D^{2}$ let us denote

$$ \rho_{1}\circ \rho_{2} = \{(x,z)| \exists y: (x,y)\in\rho_{1} \text{and } (y,z)\in \rho_{2}\} $$

Definition 18

Let Γ₂ be a set of all nonempty binary relations over D. A subset $C\subseteq {\mathcal C}^{\boldsymbol {\Gamma }_{2}}_{V}$ is called full if for any u,v ∈ V there exists only one 〈(u,v),ρ〉∈ C. A full subset $C\subseteq {\mathcal C}^{\boldsymbol {\Gamma }_{2}}_{V}$ is called path-consistent if for any 〈(u,v),ρ₁〉,〈(v,w),ρ₂〉,〈(u,w),ρ₃〉∈ C we have $\rho _{3}\subseteq \rho _{1}\circ \rho _{2}$ and for any 〈(u,u),ρ〉∈ C we have $\rho \subseteq \{(a,a)|a\in D\}$.

It is well-known that for binary constraint satisfaction problems, path consistency is equivalent to 3-local consistency [63]. Therefore, if $C\subseteq {\mathcal C}^{\boldsymbol {\Gamma }_{2}}_{V}$ is path-consistent, then the corresponding 2-SAT instance is satisfiable.

Let us introduce the set of formulas:

• 1. $\forall x \text {True} \rightarrow \pi _{2}(x, x)$

• 2. $\forall x,y \big (\pi _{1}(x, y) \rightarrow \pi _{1}(y, x)\big )$

• 3. $\forall x,y \big (\pi _{3}(x, y) \rightarrow \pi _{3}(y, x)\big )$

• 4. $\forall x,y,z \big (\pi _{2}(x, y) \wedge \pi _{2}(y, z) \rightarrow \pi _{2}(x, z)\big )$

• 5. $\forall x,y,z \big (\pi _{1} (x, y) \wedge \pi _{2}(y, z) \rightarrow \pi _{1}(x, z)\big )$

• 6. $\forall x,y,z \big (\pi _{3} (x, y) \wedge \pi _{2} (z, y) \rightarrow \pi _{3} (x, z)\big )$

• 7. $\forall x,y,z \big (\pi _{3} (x, y) \wedge \pi _{1}(y, z) \rightarrow \pi _{2}(x, z)\big )$

To any relational structure R = (V,r₁,r₂,r₃), where r_i,i ∈ [r] is a binary relation, one can correspond the full subset:

$$ C({\mathbf R}) = \{\langle (u,v), \rho_{uv} \rangle | u,v\in V\} \subseteq {\mathcal C}^{\boldsymbol{\Gamma}_{2}}_{V} $$

where

$$ \begin{array}{llllll} \rho_{uv} = \displaystyle\bigcap\limits_{i: (u,v)\in r_{i}}{\varrho}_{i} \bigcap\limits_{i: (u,v)\in {r^{T}_{i}}}{{\varrho}^{T}_{i}}, \text{ if } u\ne v \\ \rho_{uu} =\displaystyle \bigcap\limits_{i: (u,u)\in r_{i}}{\varrho}_{i} \bigcap\limits_{i: (u,u)\in {r^{T}_{i}}}{{\varrho}^{T}_{i}} \cap \{(a,a)|a\in D\} \end{array} $$

Lemma 8

If R = (V,r₁,r₂,r₃) satisfies the formulas 1-7 and $r_{1}\cap r_{2}\cap r_{3}\cap {r^{T}_{2}}=\emptyset$, r₁ ∩ r₃ ∩{(u,u)|u ∈ V } = ∅, then C(R) is path-consistent.

Proof

Properties 2 and 3 claim that r₁ and r₃ are symmetric relations, therefore we have $r_{1} = {r^{T}_{1}}$ and $r_{3} = {r^{T}_{3}}$. Since $r_{1}\cap r_{2}\cap r_{3}\cap {r^{T}_{2}}=\emptyset$, then the set $\{{\varrho }_{i}| (u,v)\in r_{i}\}\cup \{{{\varrho }^{T}_{i}}| (u,v)\in {r^{T}_{i}}\} \ne \{{\varrho }_{1},{\varrho }_{2},{\varrho }_{3},{{\varrho }^{T}_{2}}\}$ for any (u,v). Since $\bigcap _{a\in A} a\ne \emptyset$ for any proper subset $A\subset \{{\varrho }_{1},{\varrho }_{2},{\varrho }_{3},{{\varrho }^{T}_{2}}\}$, then ρ_uv≠∅ for any u≠v.

Due to the property 1, we have $(u,u)\in r_{2}\cap {r_{2}^{T}}$ for any u ∈ V. Also, (u,u)∉r₁ ∩ r₃ because of r₁ ∩ r₃ ∩{(v,v)|v ∈ V } = ∅. Therefore, for any u ∈ V, the set $\{{\varrho }_{i}| (u,u)\in r_{i}\}\cup \{{{\varrho }^{T}_{i}}| (u,u)\in {r^{T}_{i}}\}$ is a proper subset of {ϱ₁,ϱ₃}. Thus, ρ_uu≠∅ and $\rho _{uu} \subseteq \{(a,a)| a\in D\}$.

Note that for any u≠v: a) (0,0)∉ρ_uv if and only if (u,v) ∈ r₁, b) (1,1)∉ρ_uv if and only if (u,v) ∈ r₃, c) (1,0)∉ρ_uv if and only if (u,v) ∈ r₂, and d) (0,1)∉ρ_uv if and only if (v,u) ∈ r₂.

Let us prove that $\rho _{uw}\subseteq \rho _{uv}\circ \rho _{vw}$ for any u,v,w ∈ V. Let us first consider the case of distinct u,v,w. Let (a,c) ∈ ρ_uw. Our goal is to show that there exists b such that (a,b) ∈ ρ_uv and (b,c) ∈ ρ_vw. Let us prove the last statement by reductio ad absurdum. Assume that for any b we have (a,b)∉ρ_uv, (b,c)∉ρ_vw and (a,c) ∈ ρ_uw.

There are 4 possibilities for (a,c): (0,0), (1,1), (0,1) and (1,0). Let us list all of them and check that (a,b)∉ρ_uv and (b,c)∉ρ_vw and (a,c) ∈ ρ_uw cannot hold for any b ∈{0,1}.

The case (a,c) = (0,0): (0,b)∉ρ_uv and (b,0)∉ρ_vw for b ∈{0,1} implies $(u,v)\in r_{1}\cap {r^{T}_{2}}$ and (v,w) ∈ r₁ ∩ r₂. Due to the property 5 we have (u,w) ∈ r₁ and this contradicts to (0,0) ∈ ρ_uw.

The case (a,c) = (1,1): (1,b)∉ρ_uv and (b,1)∉ρ_vw for b ∈{0,1} implies (u,v) ∈ r₃ ∩ r₂ and $(v,w)\in r_{3}\cap {r^{T}_{2}}$. Due to the property 6 we have (u,w) ∈ r₃ and this contradicts to (1,1) ∈ ρ_uw.

The case (a,c) = (0,1): (0,b)∉ρ_uv and (b,1)∉ρ_vw for b ∈{0,1} implies $(u,v)\in r_{1}\cap {r^{T}_{2}}$ and $(v,w)\in r_{3}\cap {r^{T}_{2}}$. Due to the property 4 we have (w,u) ∈ r₂ and this contradicts to (0,1) ∈ ρ_uw.

The case (a,c) = (1,0): (1,b)∉ρ_uv and (b,0)∉ρ_vw for b ∈{0,1} implies (u,v) ∈ r₃ ∩ r₂ and (v,w) ∈ r₁ ∩ r₂. Due to the property 4 we have (u,w) ∈ r₂ and this contradicts to (1,0) ∈ ρ_uw.

It remains to check path-consistency property for any triple of variables u,v,w ∈ V where either u = w≠v or u = v≠w (i.e. 2-local consistency). The case u = v = w is trivial.

Let us check the case u = w≠v. Let (a,a) ∈ ρ_uu. Let us assume that for any b ∈ D we have (a,b)∉ρ_uv. The case a = 0 gives (0,0) ∈ ρ_uu, (0,0),(0,1)∉ρ_uv, and therefore, (u,u)∉r₁, $(u,v)\in r_{1}\cap {r_{2}^{T}}$. From property 5 we conclude (u,u) ∈ r₁ and obtain a contradiction. The case a = 1 gives (1,1) ∈ ρ_uu, (1,0),(1,1)∉ρ_uv, and therefore, (u,u)∉r₃, (u,v) ∈ r₃ ∩ r₂. From property 6 we conclude (u,u) ∈ r₃ and obtain a contradiction.

Finally, let us check the case u = v≠w. Let (a,c) ∈ ρ_uw and for any b ∈ D we have (a,b)∉ρ_uu,(b,c)∉ρ_uw.

The case (a,c) = (0,0) gives (0,0) ∈ ρ_uw, (0,b)∉ρ_uu,(b,0)∉ρ_uw. The last is equivalent to (u,w)∉r₁, (u,u) ∈ r₁, (u,w) ∈ r₁ ∩ r₂. From property 5 we conclude (u,w) ∈ r₁ and obtain a contradiction.

The case (a,c) = (1,1) gives (1,1) ∈ ρ_uw, (1,b)∉ρ_uu,(b,1)∉ρ_uw. The last is equivalent to (u,w)∉r₃, (u,u) ∈ r₃, $(u,w)\in r_{3}\cap {r^{T}_{2}}$. From property 6 we conclude (u,w) ∈ r₃ and obtain a contradiction.

The case (a,c) = (0,1) gives (0,1) ∈ ρ_uw, (0,b)∉ρ_uu,(b,1)∉ρ_uw. The last is equivalent to $(u,w)\notin {r^{T}_{2}}$, (u,u) ∈ r₁, $(u,w)\in r_{3}\cap {r^{T}_{2}}$. From property 7 we conclude (w,u) ∈ r₂ and obtain a contradiction.

The case (a,c) = (1,0) gives (1,0) ∈ ρ_uw, (1,b)∉ρ_uu,(b,0)∉ρ_uw. The last is equivalent to (u,w)∉r₂, (u,u) ∈ r₃, (u,w) ∈ r₁ ∩ r₂. From property 7 we conclude (u,w) ∈ r₂ and obtain a contradiction. Thus, the lemma is proved. □

Corollary 2

Let L be the set of formulas 1-7 and $L^{\text {stop}} = \{\pi _{1}(x,y)\wedge \pi _{2}(x,y)\wedge \pi _{3}(x,y) \wedge \pi _{2}(y,x)\rightarrow \mathrm {F}, \pi _{1}(x,x)\wedge \pi _{3}(x,x) \rightarrow \mathrm {F}\}$. Then, Dense(Γ) can be solved by the Datalog program L ∪ L^stop.

Proof

Let R be an instance of Dense(Γ). If Hom(R,Γ) = ∅, then Hom(R^L,Γ) = ∅. By construction, R^L satisfies properties 1-7. If ${r^{L}_{1}}\cap {r^{L}_{2}}\cap {r^{L}_{3}} \cap ({r^{L}_{2}})^{T} = \emptyset$ and ${r^{L}_{1}}\cap {r^{L}_{3}}\cap \{(v,v)|v\in V\}=\emptyset$, then, by Lemma 8, the subset C(R^L) is path-consistent (and therefore, is satisfiable). The last contradicts to Hom(R^L,Γ) = ∅. Therefore, either ${r^{L}_{1}}\cap {r^{L}_{2}}\cap {r^{L}_{3}} \cap ({r^{L}_{2}})^{T} \ne \emptyset$ or ${r^{L}_{1}}\cap {r^{L}_{3}}\cap \{(v,v)|v\in V\}\ne \emptyset$. In that case the Datalog program will identify the emptiness of Hom(R,Γ) by applying the rule $\pi _{1}(x,y)\wedge \pi _{2}(x,y)\wedge \pi _{3}(x,y) \wedge \pi _{2}(y,x)\rightarrow \mathrm {F}$ to $(u,v)\in {r^{L}_{1}}\cap {r^{L}_{2}}\cap {r^{L}_{3}} \cap ({r^{L}_{2}})^{T}$ or the rule $\pi _{1}(x,x)\wedge \pi _{3}(x,x) \rightarrow \mathrm {F}$ to $(u,u)\in {r^{L}_{1}}\cap {r^{L}_{3}}\cap \{(v,v)|v\in V\}$.

Let us now consider the case Hom(R^L,Γ)≠∅. In that case we have ${r^{L}_{1}}\cap {r^{L}_{2}}\cap {r^{L}_{3}} \cap ({r^{L}_{2}})^{T} = \emptyset$, ${r^{L}_{1}}\cap {r^{L}_{3}}\cap \{(v,v)|v\in V\}=\emptyset$ and the subset C(R^L) is path-consistent. A well-known application of Baker-Pixley theorem to languages with a majority polymorphism [64] gives us that path-consistency (or, 3-consistency) implies global consistency. Thus, any 3-consistent solution can be globally extended, i.e.

$$ \text{pr}_{u,v} \text{Hom}({\mathbf R}, \boldsymbol{\Gamma}) = \text{pr}_{u,v} \text{Hom}({\mathbf R}^{L}, \boldsymbol{\Gamma}) = \rho_{u,v} $$

for any $\langle (u,v), \rho _{uv}\rangle \in C({\mathbf R}^{L})$. Thus,

$$ \bigcap\limits_{h\in \text{Hom}({\mathbf R}, \boldsymbol{\Gamma})} h^{-1}({\varrho}_{i}) = \{(u,v)| \text{pr}_{u,v} \text{Hom}({\mathbf R}, \boldsymbol{\Gamma})\subseteq {\varrho}_{i}\} = \{(u,v)| \rho_{u,v}\subseteq {\varrho}_{i}\} \subseteq {r^{L}_{i}} $$

The last implies that (R^L,Γ) is a maximal pair, and this completes the proof. □

17 Conclusion and open questions

We studied the size of an implicational system Σ corresponding to a densification operator on a set of constraints for different constraint languages. It turns out that only for bounded width languages this size can be bounded by a polynomial of the number of variables. This naturally led us to more efficient algorithms for the densification and the sparsification tasks.

An unresolved issue of the paper is a relationship (equality?) between the following classes of constraint languages: a) core languages with a weak polynomial densification operator, b) core languages of bounded width. Also, the complexity classification of Dense(Γ) for the general domain D is still open.