Tractability of Quantified Temporal Constraints To The Max

For a fixed structure $\Gamma$ with finite relational signature $\tau$, the constraint satisfaction problem of  $\Gamma$, denoted by $\operatorname{CSP}(\Gamma)$, is the problem of deciding whether a given sentence of the form $\exists x_{1}\dots\exists x_{n}(\psi_{1}\wedge\dots\wedge\psi_{m})$ is true in $\Gamma$; here, each $\psi_{i}$ is an atomic $\tau$-sentence, that is, of the form $R(y_{1},\dots,y_{k})$ for $R\in\tau$ and $y_{1},\dots,y_{k}\in\{x_{1},\dots,x_{n}\}$. The given sentence is called an instance of $\operatorname{CSP}(\Gamma)$, and the formulas $\psi_{i}$ are called the constraints of the instance. The set of relations of $\Gamma$ is called the constraint language of $\Gamma$.

A very active research program attempts to classify the computational complexity of $\operatorname{CSP}(\Gamma)$ for all finite structures $\Gamma$; see e.g. the collection of survey articles [16]. Particularly interesting are structures $\Gamma$ that are maximally tractable; the idea is that those structures $\Gamma$ are the structures that sit at the frontier between the easy and the hard CSPs. The notion of maximal tractability also applies to structures $\Gamma$ with an infinite relational signature. We say that $\Gamma$ is maximally tractable for the CSP with respect to a class $\mathcal{C}$ of relations over the same domain (and in this case we also say that the constraint language of $\Gamma$ is maximally tractable) if

• •

  for every structure $\Gamma^{\prime}$ whose constraint language is finite and contained in the constraint language of $\Gamma$, the problem $\operatorname{CSP}(\Gamma^{\prime})$ is in P, and

• •

  for every set of relations ${\mathcal{R}}\subseteq{\mathcal{C}}$ that properly contains the constraint language of $\Gamma$ there exists a structure $\Gamma^{\prime\prime}$ with a finite constraint language that is contained in $\mathcal{R}$ such that $\operatorname{CSP}(\Gamma^{\prime\prime})$ is NP-hard.

Surprisingly often, when $\Gamma$ is maximally tractable for the CSP with respect to a class of relations, the more expressive quantified constraint satisfaction problem for $\Gamma$, denoted by $\operatorname{QCSP}(\Gamma)$, can be solved in polynomial time as well. The problem $\operatorname{QCSP}(\Gamma)$ is defined analogously to $\operatorname{CSP}(\Gamma)$, with the difference that, in addition to existential quantification, universal quantification is also permitted in the input. That is, an instance of $\operatorname{QCSP}(\Gamma)$ is a sentence of the form $Q_{1}v_{1}\dots Q_{n}v_{n}(\psi_{1}\wedge\dots\wedge\psi_{m})$, for $Q_{1},\dots,Q_{n}\in\{\exists,\forall\}$, to be evaluated in $\Gamma$.

While one might expect that $\operatorname{QCSP}(\Gamma)$ is typically harder than $\operatorname{CSP}(\Gamma)$, for the following structures $\Gamma$ both $\operatorname{CSP}(\Gamma)$ and $\operatorname{QCSP}(\Gamma)$ are polynomial-time decidable:

1. (1)

   2-element structures $\Gamma$ preserved by $\min$ or by $\max$ [20];

2. (2)

   2-element structures $\Gamma$ preserved by the majority operation [1];

3. (3)

   2-element structures $\Gamma$ preserved by the minority operation [15];

4. (4)

   structures $\Gamma$ preserved by a near-unanimity operation [13];

5. (5)

   structures $\Gamma$ preserved by a Maltsev operation [9];

6. (6)

   structures $\Gamma$ that contain a unary relation $U$ for every subset of its domain, and $\operatorname{CSP}(\Gamma)$ is tractable [5].

See [14] for a survey on the state of the art of complexity classification for $\operatorname{QCSP}(\Gamma)$ for finite structures $\Gamma$.

Maximal tractability of a structure $\Gamma$ for the QCSP is defined analogously to maximal tractability of $\Gamma$ for the CSP. Note that if $\Gamma$ is maximally tractable for the CSP with respect to some class of relations $\mathcal{C}$, and if for all structures $\Gamma^{\prime}$ whose constraint language is finite and contained in the constraint language of $\Gamma$ the problem $\operatorname{QCSP}(\Gamma^{\prime})$ is in P as well, then $\Gamma^{\prime}$ is maximally tractable for the QCSP with respect to $\mathcal{C}$ as well. This is for instance the case for all the maximally tractable structures $\Gamma$ that appear in (1)-(6) above (each of those 6 items contains structures $\Gamma$ that are maximally tractable for the CSP with respect to the class of all relations over the same domain). If structures that are maximally tractable for the CSP are also maximally tractable for the QCSP, then this is interesting because it tells us that in this case the restriction to only existential quantifiers does not make a hard problem easy.

In this article we study this transfer of maximal tractability for the CSP to maximal tractability for the QCSP for structures $\Gamma$ with an infinite domain. One of the best-understood classes of infinite structures is the class of all highly set-transitive structures; these are the structures $\Gamma$ with the property that for all finite subsets $A$, $B$ of equal size, there exists an automorphism of $\Gamma$ which sends $A$ to $B$. By a theorem due to Cameron [10], this is the case if and only if $\Gamma$ is isomorphic to a structure with domain ${\mathbb{Q}}$ whose relations are first-order definable over $({\mathbb{Q}};<)$, i.e., for each relation $R$ of $\Gamma$ there is a first-order formula that defines $R$ over $({\mathbb{Q}};<)$ (without parameters). In the context of constraint satisfaction, the constraint languages of highly set-transitive structures have also been called temporal constraint languages, since many problems in qualitative temporal reasoning can be formulated as $\operatorname{CSP}(\Gamma)$ for such structures $\Gamma$ (see [7, 8] for examples). We refer to a relation having a first-order definition in $({\mathbb{Q}};<)$ as a temporal relation. From now on, maximal tractability will be with respect to the class of all temporal relations over ${\mathbb{Q}}$.

The class of temporal constraint languages is very rich, and often provides examples and counterexamples for CSPs of infinite structures $\Gamma$. For example, for finite structures $\Gamma$ it is known that $\operatorname{CSP}(\Gamma)$ can be solved by Datalog if and only if the core of $\Gamma$ expanded by constants does not interpret primitively positively the structure $({\mathbb{Z}}_{p};\{(x,y,z)\;|\;x-y+z=1\})$; this follows from the main result in [2] in combination with [17]. The same statement is false already for the simple structure $({\mathbb{Q}};\{(x,y,z)\;|\;x>y\vee x>z\})$, which does not interpret $({\mathbb{Z}}_{p};\{(x,y,z)\;|\;x-y+z=1\})$ primitively positively with constants¹¹1Since it has the polymorphism $f(x,y)=\min(x,y)$ satisfying $\forall x,y(f(x,y)=f(y,x))$; see [3] for an introduction to primitive positive interpretations and the related universal algebra., but which cannot be solved by Datalog; see [8]. The list of phenomena that are specific to infinite-domain constraint satisfaction and that are exemplified already for temporal constraint languages can be prolonged easily; we refer to [3] for more detail.

The complexity of $\operatorname{CSP}(\Gamma)$ has been completely classified for structures $\Gamma$ with a temporal constraint language (due to [7]; also see [3]). In this paper we visit some of the CSP maximally tractable temporal constraint languages and study their $\operatorname{QCSP}$. For the languages that we study, we show that even the $\operatorname{QCSP}$ is polynomial-time tractable. Our results are as follows.

• •

  When all relations of $\Gamma$ are preserved by the operation $(x,y)\mapsto\min(x,y)$, then $\operatorname{QCSP}(\Gamma)$ is in P.

• •

  When all relations in $\Gamma$ are preserved by the operation $\operatorname{mx}$ (introduced in [7]), then $\operatorname{QCSP}(\Gamma)$ is in P. As with $\min$, the operation $\operatorname{mx}$ is binary and commutative; we repeat the definition in Section 3.3.

We complement those results by giving intuitive syntactic descriptions of the temporal relations that are preserved by $\min$, and likewise of those that are preserved by $\operatorname{mx}$. That is, we present a class of syntactically restricted first-order formulas with the property that a temporal relation is preserved by min if and only if it has a definition by a formula from the class, and likewise for $\operatorname{mx}$. Those characterizations are important since they give a more explicit description of the allowed constraints in the respective QCSPs. A similar syntactic description of relations over finite domains preserved by $\min$ can be found in [19].

The results that we present for temporal constraint languages preserved by $\min$ also hold in analogous form for those that are preserved by $\max$. The operations $\min$ and $\max$ are dual in the following sense: $\max(x,y)=-\min(-x,-y)$. Similarly, the operation $\operatorname{mx}$ has the dual operation $(x,y)\mapsto-\operatorname{mx}(-x,-y)$, and again the results that we have obtained for $\operatorname{mx}$ also hold analogously for the dual of $\operatorname{mx}$.

Let $f\colon D^{k}\rightarrow D$ be a function. When $t^{1}=(t^{1}_{1},\dots,t^{1}_{m}),\dots,t^{k}=(t^{k}_{1},\dots,t^{k}_{m})\in D^{m}$, then $f(t^{1},\dots,t^{k})$ denotes the tuple $(f(t_{1}^{1},\dots,t^{k}_{1}),\dots,f(t_{m}^{1},\dots,t^{k}_{m}))$ from $D^{m}$ that we obtain by applying $f$ componentwise. A function $f\colon D^{k}\rightarrow D$ preserves a relation $R\subseteq D^{m}$ if for all $t^{1},\dots,t^{k}\in R$ it holds that $f(t^{1},\dots,t^{k})\in R$. If $f$ preserves all relations of a structure $\Gamma$, we say that $f$ is a polymorphism of $\Gamma$.

Example. The operation $\min\colon{\mathbb{Q}}^{2}\rightarrow{\mathbb{Q}}$ that maps two rational numbers to the minimum of the two numbers is a polymorphism of the temporal constraint language $({\mathbb{Q}};\leq,<)$, but not of the temporal constraint language $({\mathbb{Q}};\neq)$, since it maps for instance the tuples $(1,0)\in\mathop{\neq}$ and $(0,1)\in\mathop{\neq}$ to $(0,0)\notin\mathop{\neq}$.

See Figure 1 for an illustration of the operation $\min$. In diagrams for binary operations $f$ as in Figure 3, we draw a directed edge from $(a,b)$ to $(a^{\prime},b^{\prime})$ if $f(a,b)<f(a^{\prime},b^{\prime})$. Unoriented lines in rows and columns of picture for an operation $f$ relate pairs of values that get the same value under $f$.

A non-trivial relation that is preserved by $\min$ is the ternary relation defined by the formula $x_{1}>x_{2}\vee x_{1}>x_{3}$, and the ternary relation $U$ defined as follows.

Another important operation for temporal constraint satisfaction is the binary operation ‘mx’, which is defined as follows [7].

where $\alpha$ and $\beta$ are unary operations that preserve $<$ such that $\alpha(x)<\beta(x)<\alpha(x+\varepsilon)$ for all $x\in\mathbb{Q}$ and all $0<\varepsilon\in\mathbb{Q}$ (see Figure 2). It is not difficult to show that such operations $\alpha,\beta$ do exist; see [7].

Note that mx does not preserve the relation $\leq$. It also does not preserve the relation $U$ introduced above. An example of a relation that is preserved by mx is the ternary relation $X$ defined as follows.

Finally, let $\operatorname{pp}$ be an arbitrary binary operation on $\mathbb{Q}$ such that $\operatorname{pp}(a,b)\leq\operatorname{pp}(a^{\prime},b^{\prime})$ iff one of the following cases applies:

• •

  $a\leq 0$ and $a\leq a^{\prime}$

• •

  $0<a$, $0<a^{\prime}$, and $b\leq b^{\prime}$.

Clearly, such an operation exists. For an illustration, see the left diagram in Figure 3. The right diagram of Figure 3 is an illustration of the $\operatorname{dual-pp}$ operation. The name of the operation $\operatorname{pp}$ is derived from the word ‘projection-projection’, since the operation behaves as a projection to the first argument for negative first argument, and a projection to the second argument for positive first argument.

The following two propositions have been shown in [7].

A straightforward corollary of Proposition 2.1 and Proposition 2.2 is that the sets of temporal relations preserved by $\min$ and by $\operatorname{mx}$, respectively, are maximally tractable constraint languages.

The set of temporal relations that is preserved by $\min$ is a proper subset of the set of temporal relations that is preserved by $\operatorname{pp}$ (see [7]); e.g., the relation $\{(x,y,z)\in{\mathbb{Q}}^{3}\;|\;(x=y\wedge y<z)\vee(x>y\wedge y=z)\}$ is preserved by $\operatorname{pp}$, but not by $\min$ and not by $\operatorname{mx}$. Indeed, the CSP for the temporal constraint language that just contains this ternary relation is NP-hard.

It is known that the structure $({\mathbb{Q}};<)$ has quantifier-elimination [18], that is, for every first-order formula $\phi$ there exists a quantifier-free formula that is equivalent to $\phi$ over $({\mathbb{Q}};<)$ (we always allow equality $=$ in our formulas). We will call such a quantifier-free formula over the signature $\{<\}$ a temporal formula. For the sake of presentation, we write temporal formulas using all symbols in $\{<,>,\leq,\geq,=,\neq\}$. Let $\phi_{R}$ be a temporal formula that defines a temporal relation $R$. For a tuple $t\in R$ and a variable $v$ occurring in $\phi_{R}$, we write $t(v)$ to indicate the value in $t$ corresponding to the variable $v$.

It is also well-known that $({\mathbb{Q}};<)$ is a homogeneous structure [21], that is, every isomorphism between finite substructures extends to an automorphism. The set of automorphisms of $({\mathbb{Q}};<)$ will be denoted by $\operatorname{Aut}({\mathbb{Q}};<)$. A set of the form $\{\alpha(t_{1}),\ldots,\alpha(t_{k})\mid\alpha\in\operatorname{Aut}({\mathbb{Q}};<)\}$ is called an orbit of $k$-tuples (the orbit of $(t_{1},\ldots,t_{k})$). It is well known that every $k$-ary temporal relation is a union of orbits of $k$-tuples.

Let $\phi_{1}$ and $\phi_{2}$ be two temporal formulas. We say that $\phi_{1}$ entails $\phi_{2}$ if and only if $({\mathbb{Q}};<)\models\forall v_{1},\dots,v_{n}(\phi_{1}\Rightarrow\phi_{2})$. We also say that an $n$-ary temporal relation $R$ entails $\phi$ if and only if $({\mathbb{Q}};<)\models\forall v_{1},\dots,v_{n}(\phi_{R}(v_{1},\ldots v_{n})\Rightarrow\phi)$, where $\phi_{R}$ is a temporal formula defining $R$. We will use the following fact, which follows directly from the definition of entailment.

In this section, we prove the following theorem.

Let $\Gamma$ be a relational $\tau$-structure. Formulas of the form

where each $\psi_{i}$ is of the form $R(y_{1},\dots,y_{k})$ for $R\in\tau$, and where $Q_{1},\dots,Q_{n}\in\{\exists,\forall\}$, will be called quantified constraint formulas (over $\Gamma)$. Existentially quantified variables are typically (but not exclusively) denoted by $x,x_{1},x_{2},\dots$, and universally quantified variables by $y,y_{1},y_{2},\dots$.