FMT 8a: Constraint Satisfaction Problems

$% \usepackage{amsmath} % \usepackage{amsfonts} % \usepackage{amssymb} % create the definition symbol \def\bydef{\stackrel{\text{def}}{=}} \newcommand{\qed}{\mbox{ } \Box} \newcommand{\set}[1]{\{#1\}} \newcommand{\eps}{\varepsilon} \newcommand{\NN}{\mathbb N} \newcommand{\Nat}{\mathbb N} \newcommand{\RR}{\mathbb R} \newcommand{\Aa}{\mathcal A} \newcommand{\Bb}{\mathcal B} \newcommand{\Cc}{\mathcal C} \newcommand{\Dd}{\mathcal D} \newcommand{\Ll}{\mathcal L} \newcommand{\str}[1]{\mathbb {#1}} \renewcommand{\implies}{\rightarrow} \newcommand{\lor}{\vee} \newcommand{\land}{\wedge} \renewcommand{\phi}{\varphi} \renewcommand{\subset}{\subseteq} \newcommand{\models}{\vDash} \DeclareMathOperator{\dom}{Dom} \DeclareMathOperator{\ifp}{ifp} \DeclareMathOperator{\lfp}{lfp} \DeclareMathOperator{\gfp}{gfp} \DeclareMathOperator{\tcl}{tcl} \DeclareMathOperator{\ln}{ln} $

We discuss the basics of Constraint Satisfaction Problems (CSPs). Some basic facts concerning the algebraic approach to CSPs are presented in the next post.

First definition. A CSP instance consists of:

  • A finite set of variables
  • A finite set of values
  • A set of constraints, where each constraint is a pair of the form $(\bar v,R)$, where $\bar v$ is a tuple of variables of some length $n$ and $R$ is a set of $n$-tuples of values, i.e., an $n$-ary relation over the set of values.

An assignment is a mapping $f$ from the set of variables to the set of values. An assignment $f$ satisfies a constraint $(\bar v,R)$, where $\bar v=(v_1,\ldots,v_n)$, if the tuple of values $(f(v_1),\ldots,f(v_n))$ belongs to the set $R$. A solution to the instance is an assignment which satisfies all constraints.

Example. Consider an instance of 3-SAT $\phi$, i.e. a formula in conjunctive normal form, whose clauses are disjuncts of three literals, and each literal is a variable or negated variable. We construct a CSP instance whose variables are the variables of $\phi$, the values are the booleans $0,1$, and for each clause $\alpha$, there is a constraint $(t,R)$ consisting of the three variables appearing in $\alpha$, and the set  of triples in $\set{0,1}^3$ which satisfy $\alpha$. For instance, if $\alpha=(x\lor \neg y\lor z)$ then there is a constraint $(t,R)$ where $t=(x,y,z)$ and $$R=\set{0,1}^3-\set{(0,0,0)}.$$ A solution to this instance is the same thing as a solution to the formula $\phi$.

The Constraint Satisfaction Problem is the following decision problem:

Input: A CSP instance

Decide: Does the instance have a solution?

The problem is in NP, since for a given assignment it can verified in polynomial time (with respect to the size of the input) whether it is a solution. The problem is also NP-complete, since as we saw in the example above, 3-SAT reduces to the CSP.

Second definition. The Constraint Satisfaction Problem is the following problem.

Input: Two relational structures $\str A,\str T$

Decide: Does $\str A$ map homomorphically to $\str T$?

The problems defined by the two definitions are equivalent. Indeed, given a CSP instance, we define:

  • The signature $\Sigma$ consisting of one symbol $R$ per each relation $R$ which occurs in some constraint of the instance,
  • $\str A$ as a relational structure whose domain consists of the variables, and for each constraint $(t,R)$, we assert that $R(t)$ holds in $\str A$
  • $\str T$ as a relational structure whose domain is the set of values, and the interpretation of the symbol $R$ is the relation $R$.

Then a solution to the instance is the same thing as a homomorphism from $\str A$ to $\str T$. Conversely, given two structures $\str A$, $\str T$ over a signature $\Sigma$, we define an instance such that:

  • The variables are the elements of $\str A$
  • The values are the elements of $\str T$
  • For each tuple $t\in R(\str A)$ there is a constraint $(t,R(\str T))$.

A homomorphism form $\str A$ to $\str T$ is then the same thing as a solution to the instance.

Example. Let $\Sigma$ be the graph signature, consisting of one binary relation $E$. If $\str T$ is an undirected $k$-clique, and $\str A$ is any structure over $\Sigma$, then $\str A\rightarrow \str T$ if and only if the undirected graph underlying $\str A$ is $k$-colorable.

In particular, $k$-colorability reduces easily to a Constraint Satisfaction Problem. It is known that $k$-colorability is NP-complete for $k>2$ and in P for $k\le 2$.

 

This suggests that it might be a good idea to classify the complexity of Constraint Satisfaction Problems by fixing the structure $\str T$.

In the case when $\str T$ is fixed, and not part of the input, then we say that the decision problem described in the second definition is a CSP problem over the template $\str T$, and we denote this decision problem by CSP($\str T)$. In this case, we allow the signature of $\str A$ to be a subset of the signature of $\str T$, assuming that all the remaining relations are interpreted as empty relations in $\str A$. This will allow to use templates over infinite signatures, which is useful for certain problems (in general, one could even allow the template $\str T$ to be an infinite structure; this is also useful in many situations).

As argued above, the problem CSP($\str T$) is NP-complete in the case when $\str T$ is the undirected 3-clique. When $\str T$ is the $k$-clique, then CSP($\str T$) is equivalent to $k$-colorolability. In particular, for $k=2$, the problem CSP($\str T)$ becomes tractable (it is even in LogSpace). The CSP classification program is the program of determining the complexity of CSP($\str T$), depending on $\str T$. The complexity of a template $\str T$ is the complexity of CSP($\str T$).

Example. There is a single template which works for all instances originating from 3-SAT (see the first example in this post). This template has two elements, $0$ and $1$, and eight ternary relations $R_{ijk}$ where $i,j,k\in \set{0,1}$, where $$R_{ijk}=\set{0,1}^3-\set{(i,j,k)}.$$

Note that not only 3-SAT reduces to the CSP over this template, but also every instance of CSP over this template is naturally viewed as an instance of 3-SAT.

Similarly, instances of 2-SAT are over a common template which also has two elements $0$ and $1$, and four binary relations $R_{ij}$ defined analogously to the above relations. The template for 3-SAT is NP-complete, while the template for 2-SAT is in PTime, since 2-SAT is in PTime.

Example. Consider a system of linear equations over the two element field $\mathbb Z_2$, with each equation of the form $x+y+z=i$ (for $i\in\mathbb Z_2$). Such a system  can be viewed as an instance over the following template: its elements are $0,1$, and there are two relations: $R_0,R_1$, where $R_i=\set{(x,y,z):x+y+z=i}$. Conversely, any instance over this template can be seen as a system of linear equations of the specified form. In particular, this template is in P, since systems of linear equations can be solved by Gaussian elimination.

The Feder-Vardi conjecture is the following:

Dichotomy Conjecture. For a fixed template $\str T$, the CSP problem over the template $\str T$ is either NP-complete or is in P.

Recall that due to Ladner’s theorem, if P≠NP, then there exist so-called NP-intermediate problems, which are in NP-P, but are not NP-complete. The dichotomy conjecture states that no CSP problem over a fixed template $\str T$ is NP-intermediate.

Is it possible to effectively characterize tractable templates? Which features of a template $\str T$ determine the complexity of the associate CSP problem? It turns out that algebra is an answer – see below.

Third definition. We give yet another equivalent formulation of the CSP problem.

The pp-theory of a structure $\str T$ is the set of pp-sentences (conjunctive queries without free variables – see this post) which hold in $\str T$. The pp-theory can be seen as a decision problem:

Input: A pp-sentence $\phi$ and a structure $\str T$

Decide: Does $\phi$ hold in $\str T$?

Since $\phi$ holds in $\str T$ if and only if $A_\phi$ maps homomorphically to $\str T$ (see this post), the above problem is clearly equivalent to the CSP problem with template $\str T$. Therefore, the CSP problem can be seen as a logical problem: decide the pp-theory of a fixed structure $\str T$. In the case when $\str T$ is fixed, the above problem is equivalent to the problem CSP($\str T$).

Consistency algorithms

Some CSP problems may be solved by a “local consistency algorithm”. There are various types of such algorithms. We present one family of such algorithms, called $(k,l)$-consistency.

Fix a pair of relational structures $\str A,\str T$ over the same signature. A partial homomorphism from $\str A$ to $\str T$ is a partial mapping $f$ from $\str A$ to $\str T$ such that for every relation symbol $R$ and for tuple $(v_1,\ldots,v_n)$ in the interpretation of $R$ in $\str A$, there is some extension $f’$ of $f$ such that $(f'(v_1),\ldots,f'(v_n))$ is in the interpretation of $R$ in $\str T$. An $l$-partial homomorphism is a partial homomorphism whose domain contains at most $l$ elements.

Fix a  two natural numbers $k<l$. Let $\mathcal F$ be a family of $l$-partial homomorphisms from $\str A$ to $\str T$. We say that the family $\mathcal F$ is:

  1. closed under restrictions if each restriction of every partial homomorphism in $\mathcal F$ also belongs to $\mathcal F$;
  2. closed under $(k,l)$-extensions if for every $k$-partial homomorphism in $\mathcal F$ and every subset $X$ of $\str A$ with at most $l$ elements containing the domain of $f$, there is a partial homomorphism $f’\in\mathcal F$ whose domain is $X$ and which extends $f$.

It is easy to see that the above properties are preserved by unions of families:

Fact. If $\mathcal F,\mathcal G$ are two families of $l$-partial homomorphisms from $\str A$ to $\str T$ whose domain contains at most $l$ elements, and both $\mathcal F$ and $\mathcal G$ are closed under restrictions, then $\mathcal F\cup \mathcal G$ is also closed under restrictions. Similarly for the property of being closed under $(k,l)$-extensions.

Corollary. There exists a unique maximal family $\mathcal F$ of $l$-partial homomorphisms from $\str A$ to $\str T$ which is closed under restrictions and under $(k,l)$-extensions.

We denote the family from the corollary by $\textrm{cons}_{k,l}(\str A,\str T)$.

Lemma 1. If there is a homomorphism from $\str A$ to $\str T$ then $\textrm{cons}_{k,l}(\str A,\str T)$ is nonempty.

Proof. This is evident, since the family of all restrictions of a fixed homomorphism to domains of size at most $l$ forms a family which is closed under restrictions and $(k,l)$-extensions.$\square$

Lemma 2. The family $\textrm{con}_{k,l}(\str A,\str T)$ can be computed in time $O({{|\str A|}\choose l}|\str T|^l).$ In particular, for a fixed template $\str T$ and parameters $k,l$, this is in polynomial time with respect to $\str A$.

Proof. This can be done by an easy fixpoint computation: start with the family of all $l$-partial homomorphisms from $\str A$ to $\str T$ and repeatedly remove from it any homomorphism if it violates either the condition 1 (i.e. some restriction of this homomorphism is not in the family) or the condition 2 (i.e. some homomorphism does not extend to a given set $X$).$\square$

The $(k,l)$-consistency algorithm is the algorithm which, for a given instance $I$ and template $\str T$ answers YES if the family $\textrm{con}_{k,l}(\str A,\str T)$ is nonempty, and NO otherwise. By Lemma 2 above, there is such an algorithm which works in polynomial time with respect to $\str A$. Moreover, by Lemma 1, if the algorithm answers NO then the instance $\str A$ has no solution.

Example. Let $\str T$ be the template which is the undirected 2-clique, and let $\str A$ be the instance which is a cycle of length 5 and vertices $x_0,\ldots,x_4$, where $x_i$ is connected with $x_{i-1}$ and $x_{i+1}$ (addition mod 5). Prove that $\textrm{cons}_{2,3}(\str A,\str T)=\emptyset$.

Exercise. Let $\str T$ again be the template which is the undirected 2-clique. Show that for an instance over this template, the $(2,3)$-consistency algorithm returns YES if and only if the instance has a solution.

We say that a template $T$ has width $(k,l)$ if for every instance $\str A$ the $(k,l)$ algorithm correctly determines whether $\str A$ has a solution, i.e., the following conditions are equivalent for any instance $\str A$:

  • $\str A$ has a solution, i.e. a homomorphism to $\str T$
  • the family $\textrm{cons}_{k,l}(\str A,\str T)$ is nonempty.

A template $\str T$ has bounded width if it has width $(k,l)$ for some numbers $k,l$. In particular, if a template $\str T$ has bounded width then the corresponding CSP is in PTime, by Lemma 2.

Example. It follows from the exercise above that the 2-clique has width $(2,3)$.

Exercise. Find a template which does not have width $(2,3)$.

Exercise. Show that the $(k,l)$-consistency algorithm can be implemented in the logic IFP. Therefore, if a template $\str T$ has width $(k,l)$, then the problem CSP($\str T$) is definable by a formula of IFP. Using the fact that IFP cannot solve systems of linear equations over $\mathbb Z_2$ proved while during the proving the CFI theorem (see the precise formulation of this fact), conclude that the template for encoding systems of linear equations over $\mathbb Z_2$ does not have bounded width. However, the complexity of this template is in P.

Remark. The fragment of IFP needed for implementing the algorithm in Lemma 2 is very simple – it is in fact the pp-fragment of FO extended by the ifp construct, i.e., it does not use the full power of first order logic, only existential quantification and conjunctions (no negations, disjunctions, and universal quantifiers). This fragment of IFP is called Datalog. Therefore, the $(k,l)$-consistency algorithm can be implemented by a negation of a Datalog program (the Datalog program answers YES if the family $\textrm{cons}_{k,l}$ is empty and NO otherwise; a negation is needed to reverse the answer). Therefore, if $\str T$ has bounded width, then $\neg$CSP($\str T$) can be solved by a negation of a Datalog program. Conversely, it is not difficult to show that if $\neg$CSP($\str T$) can be solved by a Datalog program, then it has bounded width. Feder and Vardi conjectured that the following conditions are equivalent: 1) $\str T$ does not have bounded width 2) $\str T$ can somehow “simulate” the template for solving linear equations over some finite abelian group. This conjecture has recently been confirmed by Barto, Kozik, Larose, Zadori, using the algebraic approach (see next post) and deep tools from universal algebra.

 

Extending a template by pp-definable relations

[the material in the rest of this post is not required on the exam]

We say that an $n$-ary relation $R$ is pp-definable in a structure $\str T$, if there is a pp-formula $\phi(x_1,\ldots,x_n)$ over the signature of $\str T$ such that $\str T$ satisfies

$$R(x_1,\ldots,x_n)\iff \phi(x_1,\ldots,x_n)\quad\text{for }x_1,\ldots,x_n\in\str T.$$

Example. Let $\str T$ be an undirected graph. Then the following relation is pp-definable in $\str T$:

$$\set{(x,y):\exists z. E(x,z)\land E(z,y)}.$$

Fact 1. An $n$-ary relation $R$ is pp-definable in a structure $\str T$ if and only if there exists a structure $\str A$ with distinguished elements $a_1,\ldots,a_n$ such that

$$R=\set{(f(a_1),\ldots,f(a_n))|\\ f:\str A\rightarrow \str T\text{ is a homomorphism}}.$$

This fact follows easily from this post, where a correspondence between pp-formulas and canonical structures is described. In the case of the example above, the corresponding structure has three vertices $x,y,z$ and $E=\set{(x,z),(z,y)}$, and the distinguished vertices are $x,y$.

Let $\str T’,\str T$ be two templates, possibly over different signatures $\Sigma’,\Sigma$. We say that a template $\str T’$ is pp-definable in a template $\str T$, if the domain of $\str T’$ is a pp-definable unary relation in the template $\str T$ and every relation of $\str T’$ is pp-definable in $\str T$.

Proposition 1. Suppose that $\str T’$ is pp-definable in $\str T$. Then CSP($\str T’$) reduces to CSP($\str T$) via a LogSpace reduction.

Proof. We consider the problem of deciding the pp-theory of $\str T’$ (see the third definition above). Let $\phi$ be a pp-sentence over the signature of $\str T’$. We want to decide whether $\phi$ holds in $\str T’$. To this end, we substitute each atom $R(x_1,\ldots,x_n)$ in $\phi$ by its pp-definition in $\str T$, yielding a formula $\psi$ over the signature of $\str T$. Clearly, $\phi$ holds in $\str T’$ if and only if $\psi$ holds in $\str T$. The formula $\psi$ is not exactly a pp-formula, since it is not in prefix normal form. However, it can be easily converted into one. This gives a LogSpace reduction from the pp-theory of $\str T’$ to the pp-theory of $\str T$.$\square$

It follows that by adding to a template $\str T$ all relations which are pp-definable in $\str T$ yields a template $\str T’$ (over an infinite signature) whose complexity is equivalent to the complexity of $\str T$ under LogSpace reductions.

Example. Consider the template $\str T$ for solving linear equations over $\mathbb Z_2$, in which every equation has 3 variables. Then the relation $$R^n_i=\set{(x_1,\ldots,x_n):x_1+\ldots+x_n=i}$$ is pp-definable in $\str T$. This follows from the fact that $R^n_i(x_1,\ldots,x_n)$ holds if and only if there exist elements $s_1,\ldots,s_n$ such that the following equations hold over $\mathbb Z_2$:

\begin{align*}
s_1&=x_1\\
s_2&=s_1+x_2\\
s_3&=s_2+x_3\\
&\cdots\\
s_n&=s_{n-1}+x_n\\
s_n&=i
\end{align*}

The $k$-th equation above (for $k=2,\ldots,n$) can be expressed as $R_0(s_{k+1},s_{k},x_{k+1})$. The last equation can be expressed using the two unary relations $\set{0}$, $\set{1}$, which are pp-definable by the formulas $R_0(x,x,x)$ and $R_1(x,x,x)$, respectively.

Let $\str T’$ be the set $\set{0,1}$ extended by all relations of the form $R_i^n$ (where $i\in \set{0,1}$ and $n\in\NN$). Then $\str T’$ is pp-definable in $\str T$. The template $\str T’$ has an infinite signature, and can encode any system of linear equations over $\mathbb Z_2$, without the restriction that each equation has three variables.$\square$

It is not clear how to prove that a given relation $R$ is not pp-definable in a template $\str T$. For instance, how to show that the relation $R_{000}$ is not pp-definable in the template for 2-SAT? As we will see in the next post, algebra provides a convenient answer to this.

Leave a Reply

Your email address will not be published. Required fields are marked *