FMT 8b: Constraint Satisfaction Problems – algebraic approach

In this post, we continue the study of the complexity of Constraint Satisfaction Problems (see previous post). We introduce an algebraic tool for this, namely, polymorphisms.

Polymorphisms

Let $\str T$ be a relational structure and $X$ a finite set. By $\str T^X$ we denote the structure over the same signature as $\str T$, whose domain consists of $X$-tuples of elements of $\str T$ (i.e., mappings from $X$ to $\str T$) and the relations are defined coordinatewisely, i.e. for a relation symbol $R$ and $k$ tuples in $\str T^X$ the relation $R(t_1,\ldots,t_k)$ holds in $\str T^n$ if for each $x\in X$, the relation $R(t_1(x),\ldots,\ldots,t_k(x))$ holds in $\str T$. The typical situation is when $X=\set{0,\ldots,n-1}$, in which case we denote $\str T^X$ by $\str T^n$, and identify its elements with $n$-tuples of elements of $\str T$.

An $n$-ary polymorphism of a relational structure $\str T$ is a homomorphism from $\str T^n$ to $\str T$. In particular, a $1$-ary polymorphism is simply an endomorphism of $\str T$.

Example. Each of the $n$ projections from $\str T^n$ to $\str T$ are $n$-ary polymorphisms.

Here is an equivalent definition. Let $T$ be a set. We say that an $n$-ary function $f: T^n\to T$ preserves a relation $R\subset T^k$ if whenever the first $n$-rows of the array belong to $R$, then so does the last one, which is obtained by coordinatewise application of $f$:

$n\left\{ \begin{array}{cccccl} \sigma_1 & \sigma_2 & \sigma_3 &\cdots&\sigma_k & \in R \\ \tau_1 & \tau_2 & \tau_3 &\cdots&\tau_k &\in R \\.&.&. &. &. &\\\nu_1 & \nu_2 & \nu_3 &\cdots&\nu_k &\in R\end{array}\right.\\ \raise{8pt}f\begin{array}{cccccl}\hline\quad\ \rho_1 & \rho_2 & \rho_3& \cdots&\rho_k& \in R\end{array}$

Fact 2. A mapping $f:\str T^n\rightarrow \str T$ is a polymorphism iff it preserves every relation of $\str T$.

Example. Consider on of the relations $R_{00}$ of the template for 2-SAT, and let $T=\set{0,1}$. Let $\str T$ be the structure whose universe is $T$ and which is equipped only with the relation $R_{00}$. We will describe all unary and binary polymorphisms of $\str T$.

What are the unary polymorphisms, i.e., endomorphisms of $\str T$? The structure $\str T$ is the graph depicted below.

An endomorphism must map the vertex $1$ to itself, since it is the only vertex with a self-loop. The vertex $0$ can be mapped either to $0$ – then we get the identity mapping – or to $1$ – we obtain the constant mapping.

Now let’s study the binary polymorphisms, i.e. homomorphisms $\str T^2\to \str T$. Observe what we are actually doing is finding all solutions to an instance of a constraint satisfaction problem over the template $\str T$, where the instance is $\str T^2$. Let us denote the elements of $\str T^2$ by $00,01,10,11$.  The interpretation of $R_{00}$ in $\str T^2$ consists of those pairs $(ab,cd)$ such that $(a,c)\neq (0,0)$ and $(b,d)\neq (0,0)$. In other words, $R_{00}$ connects two vertices $ab,cd$ iff their bitwise OR is equal to $11$. The instance $\str T^2$ is depicted below.

Since $\str T^2$ has a self-loop at the node $11$, while $\str T$ has a self-loop only at $1$, a homomorphism must map $11$ to $1$. The nodes $01,10$ cannot be simultanously mapped to $0$, since they are connected by an edge, while $0$ has no self-loop.

This leaves us with 6 mappings:

• The two projections from $\str T^2$ to $\str T$
• The $\lor$ mapping: $\lor(x,y)=x\lor y$
• The mapping $g(x,y)$ titled “if $(x\lor y)$ then $f(x,y)$ else $1$” where $f$ is one of the three mappings above

Those are all the binary polymorphisms of $\str T$.$\square$

We say that a function $m:\str T^3\rightarrow \str T$ is a majority operation on $\str T$ if it satisfies $$m(x,x,y)=m(x,y,x)=m(y,x,x)=x$$ for all $x,y\in \str T$. A majority polymorphism is a polymorphism which is a majority operation.

Example. Consider the template $\str T$ associated with 2-SAT. We show that $\str T$ has a majority polymorphism. Since $\str T$ has only two elements, there is only one majority function on $\str T$: $m(a,b,c)=d$ where $d$ is the element which appears at least twice among $a,b,c$. We show that this function is a polymorphism of $\str T$, by showing that it preserves each relation of $\str T$.

Consider one of the relations of $\str T$, say $R_{00}$, and consider the situation below:

$\quad\begin{array}{ccl} \sigma_1 & \sigma_2 & \in R_{00} \\ \tau_1 & \tau_2 &\in R_{00}\\ \nu_1 & \nu_2 &\in R_{00}\end{array}\\ \raise{8pt}m\begin{array}{ccl}\hline\ \rho_1 & \rho_2 &\qquad\quad \end{array}$

Suppose that $(\rho_1,\rho_2)\not\in R_{00}$. Then it must be the case that $\rho_1=0,\rho_2=0$. Therefore, $0$ appears twice among $\sigma_1,\tau_1,\nu_1$, and appears twice among $\sigma_2,\tau_2,\nu_2$. But then one of the pairs $(\sigma_1,\sigma_2)$, $(\tau_1,\tau_2)$ or $(\nu_1,\nu_2)$ is equal to $(0,0)$, a contradiction with the assumption that each of those pairs belongs to $R_{00}$. Therefore, $(\rho_1,\rho_2)\in R_{00}$, which proves that $m$ preserves the relation $R_{00}$. An analogous argument shows that $m$ preserves every other relation of the template $\str T$.

Example. Now consider the template associated with 3-SAT. Again, since this template has two elements, there is only one majority operation. We show that this operation does not preserve the relation $R_{000}$. Indeed:

$\quad\begin{array}{cccl} 1 & 0 & 0 &\in R_{000} \\ 0 & 1 & 0 & \in R_{000}\\ 0 & 0 & 1 & \in R_{000}\end{array}\\ \raise{8pt}m\begin{array}{cccl}\hline\ 0 & 0 & 0&\not\in R_{000} \end{array}$

Theorem 2. If a template $\str T$ has a majority polymorphism, then it has width $(2,3)$. In particular, its complexity is in P.

(See previous post for the definition of bounded width).

There are templates in P which do not have a majority polymorphism.

Example. Consider the template for encoding systems of linear equations over $\mathbb Z_2$. This template is in P, but does not have a majority polymorphism – the argument is similar to the one for 3-SAT, with $R_{000}$ replaced by $R_1$. In fact, in an exercise in the previous post we saw that this template does not have bounded width.

Exercise. Show that if $\str T$ is a template whose domain has two elements, and every relation is binary, then $\str T$ has a majority polymorphism.

A $k$-ary operation $nu:\str T^k\to \str T$ is called a near unanimity if for any $x,x_1,\ldots,x_k$, $$nu(x_1,x_2,\ldots,x_k)=x$$ whenever all but at most one of the elements $x_1,\ldots,x_k$ are equal to $x$. In particular, a ternary near unanimity operation is the same thing as a majority operation.

Lemma 1. If $\str T$ admits a near unanimity polymorphism of arity $k$, then it admits one of arity $k+1$.

Proof. Define $nu'(x_1,\ldots,x_{k+1})=nu(x_1,\ldots,x_k)$.$\square$

We will prove the following result, extending Theorem 2 above.

Theorem 2′. If $\str T$ admits a $k$-ary near unanimity polymorphism then $\str T$ has width $(k-1,k)$. Moreover, a solution to an instance $\str A$ can be found by a greedy algorithm, basing on $\text{cons}_{k-1,k}(\str A,\str T)$.

Proof. Let $\str T$ be a template with a $k$-ary near unanimity polymorphism $nu$. Let $\str A$ be an instance, such that there is a nonempty $\mathcal F$ family of $k$-partial homomorphisms from $\str A$ to $\str T$ which is closed under restrictions and under $(k-1,k)$ extensions. We will construct a homomorphism from $\str A$ to $\str T$.

Lemma 2. Let $\phi$ be a partial homomorphism whose domain has $l\ge k-1$ elements, and let $a\in \str A-\textrm{Dom}(\phi)$. Then there exists a partial homomorphism $\phi’$ extending $\phi$ to $a$.

Proof. We prove the lemma by induction on $l$. For $l=k-1$, the statement follows from the fact that $\mathcal F$ is closed under $(k-1,k)$-extensions.

For the inductive step, suppose that the lemma holds for $l-1$ in place of $l$. We show that it also holds for $l$. Let $\phi$ and $a$ be as in the assumptions of the lemma. Consider any element $b\in\textrm{Dom}(\phi)$. We apply the inductive assumption to the partial mapping $\textrm{Dom}(\phi)-\set{b}$ and the element $a$, obtaining a partial mapping which is $\mathcal F$-consistent, whose domain is $\textrm{Dom}(\phi)-\set{b}\cup\set{a}$, and which agrees with $\phi$ where both mappings are defined. Let $\phi_b$ denote this mapping, extended arbitrarily to $b$. Therefore, $\textrm{Dom}(\phi_b)=\textrm{Dom}(\phi)\cup\set{a}$.

Let $b_1,\ldots,b_l$ be all the elements of the domain of $\phi$, and let $\phi_{b_1},\ldots,\phi_{b_l}$ be the associated mappings constructed as described above. Define

$$\phi'(x)=nu(\phi_{b_1}(x),\ldots,\phi_{b_l}(x)),\quad\text{for }x\in \textrm{Dom}(\phi)\cup\set{a}$$

where $nu$ is the near unanimity polymorphism of $\str T$ of arity $l$, which exists by Lemma 1. It is easy to see that $\phi’$ extends $\phi$. It remains to show that $\phi’$ is a partial homomorphism.
To this end, consider any tuple $\bar x=(x_1,\ldots,x_l)$ such that $R(\bar x)$ holds in $\str A$. We show that $\phi’$ can be extended to $X=\set{x_1,\ldots,x_l}$ yielding a mapping $\hat\phi’$ such that $R(\hat\phi'(x_1),\ldots,\hat\phi'(x_l))$ holds in $\str B$.

We use the assumption that each mapping $\phi_b$, for $b\in\textrm{Dom}(\phi)$,
can be extended to $X$, perhaps by modifying its value on $b$, yielding a mapping $\hat\phi_b$ such that $R(\hat \phi_b(x_1),\ldots,\hat \phi_b(x_l))$ holds in $\str B$. Define $\hat \phi'(x)$ as
$nu(\hat\phi_{b_1}(x),\ldots,\hat\phi_{b_l}(x))$, for $x\in \textrm{Dom}(\phi)\cup\set{a}$.

By polymorphicity of $nu$, we have $R(\hat\phi'(x_1),\ldots,\hat \phi'(x_l))$
It is easy to check that $\hat\phi’$ extends $\phi’$. Indeed, by definition, $\hat\phi'(a)=\hat\phi(a)$ and by near-unanimity, $\hat\phi'(x)=\phi(x)=\hat\phi(x)$ for $x\in\textrm{Dom}(\phi)$.

This ends the inductive proof of Lemma 2.
$\square$
As a corollary, if $\text{cons}_{k-1,k}(\str A,\str T)$ is nonempty, then there exists a homomorphism from $\str A$ to $\str T$, which can be constructed by iteratively applying Lemma 2. This proves that if $\str T$ has a near-unanimity polymorphism, then CSP($\str T$) is in polynomial time, since to determine if $\str A\rightarrow \str T$, it suffices to compute $\text{cons}_{k-1,k}(\str A,\str T)$ and test nonemptiness. Moreover, a homomorphism from $\str A$ to $\str T$ can be constructed in polynomial time from $\text{cons}_{k-1,k}(\str A,\str T)$, by iteratively applying the construction described in Lemma 2. This ends the proof of Theorem 2′.
$\square$

Polymorphisms capture complexity

[the material in the rest of this post is not required on the exam. See however the exercises below.]

We will see that the set of polymorphisms of a template $\str T$ determines the complexity of CSP($\str T$), up to LogSpace reductions. For a structure $\str T$, let $Pol(\str T)$ denote the set of all polymorphisms of $\str T$, of any finite arity (this is an infinite set, since it always contains all projections from $\str T^n$ to $\str T$). $Pol(\str T)$ is called the algebra of polymorphisms of $\str T$.

The following theorem shows that the complexity of $\str T$ is determined by its algebra of polymorphisms.

Theorem 3. Suppose that $\str T,\str T’$ are two structures over the same domain such that $Pol(\str T)\subset Pol(\str T’)$. Then $\str T’$ is pp-definable in $\str T$.

In particular, by Proposition 1 of the previous post, CSP($\str T’$) is LogSpace reducible to CSP($\str T$).

Corollary. If $Pol(\str T)=Pol(\str T’)$ then CSP($\str T’$) and CSP($\str T$) are interreducible via LogSpace reductions. In particular, $Pol(\str T)$ determines the complexity of CSP($\str T$) (up to LogSpace reductions).

Theorem 3 follows from the following lemma.

Lemma 3. The following conditions are equivalent for a relation $R$ over $\str T$:

1. $R$ is pp-definable in $\str T$
2. $R$ is preserved by all polymorphisms of $\str T$.

First we show how the lemma implies Theorem 3. Assume that $Pol(\str T)\subset Pol(\str T’)$. We will show that $\str T’$ is pp-definable in $\str T$.

Let $R$ be a relation of $\str T’$. By Fact 2, $R$ is preserved by all polymorphisms of $\str T’$. Since $Pol(\str T)\subset Pol(\str T’)$, in particular $R$ is preserved by all polymorphisms of $\str T$. According to the implication 2→1 of the lemma, $R$ is pp-definable in $\str T$. Since this applies to every relation of $\str T’$, it follows that $\str T’$ is pp-definable in $\str T$. This proves Theorem 3.$\square$

It remains to prove the lemma.

Proof of Lemma 3.

First we prove the implication 1→2. Suppose that $R$ is a pp-definable relation of arity $k$ over $\str T$. By Fact 1, there is a structure $\str A$ with distinguished elements $a_1,\ldots, a_k$ such that

\begin{align}\label{eq:ppdef}R=\set{(f(a_1),\ldots,f(a_k))|\\\notag f:\str A\rightarrow \str T\text{ is a homomorphism}}.\end{align}

We will show that $R$ is preserved under polymorphisms of $\str T$. Let $X$ be a finite set and let $$g:\str T^X\rightarrow \str T$$be a homomorphism. We will show that $g$ – treated as a polymorphism – preserves the relation $R$.

Suppose that $t_1,\ldots,t_k$ are elements of $\str T^X$ such that for each $x\in X$,

We will show that $(g(t_1),\ldots,g(t_k))\in R$.

By equation $\eqref{eq:ppdef}$ and by $\eqref{eq:rows}$, for each $x\in X$ there is a homomorphism $$f_x:\str A\rightarrow \str T$$ such that $t_i(x)=f_x(a_i)$ for $i=1,\ldots,k$. We define a mapping $$f:\str A\rightarrow \str T^X$$ in the natural way, by setting $f(a)(x)=f_x(a)$. Then, by definition of the structure $\str T^X$, $f$ is a homomorphism. Moreover, $f(a_i)=t_i$ for $i=1,\ldots,k$.

By composing $g$ with $f$ we get a homomorphism from $\str A$ to $\str T$, which maps $a_i$ to $g(t_i)$. By equation $\eqref{eq:ppdef}$ this shows that $(g(t_1),\ldots,g(t_k))\in R$. Therefore, $g$ preserves $R$, proving the implication 1→2.

We now prove the implication 2→1. Let $R\subset \str T^k$ be a relation. Consider the structure $\str T^R$. Since $R\subset \str T^k$, there are obvious projections $\pi_1,\ldots,\pi_k:R\rightarrow \str T$.

Claim. If $R\subset \str T^k$ is preserved by all polymorphisms of $\str T$, then $$R=\set{(f(\pi_1), \ldots, f(\pi_k))|\\ f:\str T^R\rightarrow \str T\text{ is a homomorphism}}$$

The claim proves the implication 2→1 of the lemma, using Fact 1.

For the ⊇ inclusion, consider any homomorphism $f:\str T^R\rightarrow \str T$. Observe that the relation $R(\pi_1,\ldots,\pi_k)$ holds in $\str T^R$. This is because for any $t=(t_1,\ldots,t_k)\in R$, $$(\pi_1(t),\ldots,\pi_k(t))=(t_1,\ldots,t_k)=t\in R.$$

Therefore, since $R$ is preserved by every polymorphism of $\str T$, it is also preserved by $f$ (since $f$ is a polymorphism of $\str T$, of “arity” $R$. Formally, we could identify the set $R$ via some bijection with the set $\set{0,\ldots,|R|-1}$; then $f$ would induce a homomorphism from $\str T^{|R|}\rightarrow \str T$, i.e., a polymorphism of arity $|R|$). Therefore, since $R(\pi_1,\ldots,\pi_k)$ holds in $\str T^R$, $R(f(\pi_1),\ldots,f(\pi_k))$ holds in $\str T$, proving the ⊇ inclusion.

For the ⊆ inclusion, consider a tuple $t=(t_1,\ldots,t_k)\in R\subset \str T^k$. Let $f_t:\str T^R\rightarrow \str T$ be the mapping which maps $\alpha\in T^R$ to $\alpha(t)$. This is the projection mapping onto the coordinate $t$ of $\str T^R$. It is therefore a homomorphism (by definition of $\str T^R$). Moreover, $f_t(\pi_i)=\pi_i(t)=t_i$. Therefore, $$(f_t(\pi_1),\ldots,f_t(\pi_k))=(t_1,\ldots,t_k)=t$$ is an element of the set on the right-hand side of the claimed equation.

This finishes the proof of the lemma.$\square$

Exercises

Exercise. Show that the relation $R_{000}$ is not pp-definable from all binary relations on $\set{0,1}$.

Exercise. Show that if $f:T^k\to T$ is a mapping which preserves every relation over the set $T$, then $f$ is a projection onto some coordinate of $\str T^k$.

Hint:   $T^k$  ɟo sʇuǝɯǝlǝ ǝɥʇ llɐ ǝɹɐ suɯnloɔ ǝsoɥʍ ǝlqɐʇ ɐ ɟo sʍoɹ ɟo ʇǝs ǝɥʇ ɹǝpᴉsuoɔ

Exercise. Show that there is a template $\str T$ with domain $\set{0,1}$ and with relations of arity at most $3$, such that every relation on $\set{0,1}$ is pp-definable in $\str T$. Conclude that the only polymorphisms of $\str T$ are the projections.

Hint: ˙uoᴉʇɐlǝɹ ʎɹɐuᴉq ʎɹɐɹʇᴉqɹɐ uɐ ǝuᴉɟǝp oʇ sʇᴉnɔɹᴉɔ uɐǝlooq ǝsn