# Tractability of Quantified Temporal Constraints To The Max

Manuel Bodirsky  Institut für Algebra, TU Dresden, Germany
<EMAIL_ADDRESS>,  Hubie Chen  Department of Computer Science,
Birkbeck, University of London, Malet Street, London WC1E 7HX, United Kingdom
<EMAIL_ADDRESS>and  Michał Wrona  Theoretical Computer Science
Department, Jagiellonian University, Poland<EMAIL_ADDRESS>
###### Abstract.

A _temporal constraint language_ is a set of relations that are first-order
definable over $({\mathbb{Q}};<)$. We show that several temporal constraint
languages whose constraint satisfaction problem is maximally tractable are
also maximally tractable for the more expressive _quantified constraint
satisfaction problem_. These constraint languages are defined in terms of
preservation under certain binary polymorphisms. We also present _syntactic_
characterizations of the relations in these languages.

###### Key words and phrases:

Highly Set-Transitive Structures, Constraint Satisfaction Problems, Temporal
Constraint Languages, Max-Closed Constraints, Quantified Constraint
Satisfaction.

The research leading to the results presented here has also received funding
from the European Research Council under the European Community’s Seventh
Framework Program (FP7/2007-2013 Grant Agreement no. 257039

The author is supported by the Swedish Research Council (VR) under grant
621-2012-3239.

##  1\. Introduction

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
constants111Since 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}$.

##  2\. Temporal Constraint Languages

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$.

Figure 1. Illustration of the operation $\min$.

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.

$\displaystyle U(x,y,z)\;\equiv\;$ $\displaystyle(x=y\wedge y<z)$
$\displaystyle\vee\;$ $\displaystyle(x=z\wedge z<y)$ $\displaystyle\vee\;$
$\displaystyle(x=y\wedge y=z)$

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

$\text{mx}(x,y):=\left\\{\begin{array}[]{l l l}\alpha(\min(x,y))&\text{if
}x\neq y\\\ \beta(x)&\text{if }x=y\end{array}\right.$

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].

Figure 2. Illustration of the operation $\operatorname{mx}$.

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.

$\displaystyle X(x,y,z)\;\equiv\;$ $\displaystyle(x=y\wedge y<z)$
$\displaystyle\vee\;$ $\displaystyle(x=z\wedge z<y)$ $\displaystyle\vee\;$
$\displaystyle(y=z\wedge y<x)$

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.

Figure 3. A visualization of $\operatorname{pp}$ (left) and
$\operatorname{dual-pp}$ (right).

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

######  Proposition 2.1 ([7]).

Let $R_{1},\dots,R_{k}$ be temporal relations that are preserved by min
(respectively, mx). Then $\operatorname{CSP}({\mathbb{Q}};R_{1},\dots,R_{k})$
is in P.

######  Proposition 2.2 ([7]).

Let $R$ be a relation with a first-order definition in $(\mathbb{Q};<)$ that
is not preserved by min (respectively, mx). Then there exists a finite set of
temporal relations $R_{1},\dots,R_{k}$ preserved by min (respectively, mx)
such that $\operatorname{CSP}({\mathbb{Q}};R,R_{1},\dots,R_{k})$ is NP-hard.

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.

##  3\. Syntactic Characterizations

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.

######  Observation 3.1.

Let $\phi_{R}:=\Phi\wedge\psi$ be a temporal formula defining a temporal
relation $R$ and $\psi^{\prime}$ a temporal formula entailed by $R$ which
entails $\psi$. Then $\phi^{\prime}_{R}:=\Phi\wedge\psi^{\prime}$ also defines
$R$.

###  3.1. Characterization of $\operatorname{pp}$-closed Relations

######  Theorem 3.2.

A temporal relation $R$ is preserved by $\operatorname{pp}$ if and only if it
can be defined as a conjunction of clauses of the form

(1) $x\neq y_{1}\vee\cdots\vee x\neq y_{k}\vee x\geq z_{1}\vee\cdots\vee x\geq
z_{l},$

where it is permitted that $l=0$ or $k=0$, in which cases the clause is a
disjunction of disequalities or contains no disequalities, respectively.

To provide the proof we fix $n$, and consider a temporal relation of arity
$n$. All the temporal formulas considered in the proof of Theorem 3.2 are
meant to have all variables in $\\{v_{1},\ldots,v_{n}\\}$. In particular we
take advantage of temporal formulas of the form:

(2) $\neg(x_{1}\circ_{1}x_{2}\wedge\cdots\wedge x_{k-1}\circ_{k-1}x_{k}),$

where $x_{1},\ldots,x_{k}\in\\{v_{1},\ldots,v_{n}\\}$ are pairwise different
and every $\circ_{i}$ is in $\\{<,=\\}$. We focus on formulas of the form (2)
that satisfy an extra condition that we call the _unambiguity condition_ which
states that if $(v_{i}=v_{j})$ occurs in $\phi$, then $i<j$. Let $\Phi_{R}$ be
the set containing all temporal formulas $\phi$ over variables
$\\{v_{1},\ldots,v_{n}\\}$ of the form (2) entailed by $R$ that satisfy the
unambiguity condition. We will now argue that $\bigwedge\Phi_{R}$ defines $R$.
Observe first that for every orbit of $n$-tuples in
$\operatorname{Aut}({\mathbb{Q}};<)$, there is the negation $\phi$ of a
formula of the form (2) that defines this orbit. We can certainly assume that
$\phi$ is over variables $\\{v_{1},\ldots,v_{n}\\}$ and satisfies the
unambiguity condition. On the other hand, to see that every such $\phi$
defines exactly one orbit observe that any two tuples
$t:=(t_{1},\ldots,t_{n})$ and
$t^{\prime}:=(t^{\prime}_{1},\ldots,t^{\prime}_{n})$ that are in the relation
defined by $\phi$ induce isomorphic substructures in $({\mathbb{Q}};<)$. By
the homogeneity of $({\mathbb{Q}};<)$, an isomorphism between such
substructures can be extended to an automorphism of $({\mathbb{Q}};<)$. It
follows that every orbit may be defined by the negation $\phi$ of a formula of
the form (2). We are now ready to prove that $R^{\prime}$ defined by
$\bigwedge\Phi_{R}$ is equal to $R$. By the definition of $R^{\prime}$ we have
that $R\subseteq R^{\prime}$. On the other hand if there is an orbit in
$\operatorname{Aut}({\mathbb{Q}};<)$ which is not in $R$, then an appropriate
formula of the form (2) is entailed by $R$. Thus $R^{\prime}$ does not contain
the orbit as well. Hence we obtain that $\bigwedge\Phi_{R}$ defines $R$.

Finally, we define an order on $\Phi_{R}$. For $\phi_{1},\phi_{2}\in\Phi_{R}$
of the form $\neg(x_{1}\circ_{1}x_{2}\wedge\cdots\wedge
x_{k-1}\circ_{k-1}x_{k})$ and $\neg(y_{1}\circ_{1}y_{2}\wedge\cdots\wedge
y_{l-1}\circ_{l-1}y_{l})$, respectively, we will say that $\phi_{1}$ is less
than $\phi_{2}$, in symbols $\phi_{1}\preceq\phi_{2}$, if $x_{1},\ldots,x_{k}$
is a subsequence of $y_{1},\ldots,y_{l}$ and $\phi_{1}$ entails $\phi_{2}$. It
is easy to see that this relation is reflexive and transitive. By the
definition of $\Phi_{R}$, we have that two formulas
$\phi_{1},\phi_{2}\in\Phi_{R}$ with the same set of variables entail each
other if and only if they are the same formula. Hence, $(\Phi_{R};\preceq)$ is
also antisymmetric, and we have defined a partial order on $\Phi_{R}$. Let
$\Phi_{R}^{m}$ be the set of minimal elements of $(\Phi_{R};\preceq)$. By
Observation 3.1, it holds that $\bigwedge\Phi^{m}_{R}$ defines $R$.

###### Proof.

To prove the right-to-left implication, it is certainly enough to show that
every relation $R_{C}$ defined by a single clause $C$ of the form (1) is
preserved by $\operatorname{pp}$. Assume on the contrary that there are
$t_{1},t_{2}\in R_{C}$ but $t_{3}=\operatorname{pp}(t_{1},t_{2})$ is not in
$R_{C}$. It implies that $t_{3}(x)=t_{3}(y_{1})=\cdots=t_{3}(y_{k})$, and
hence by the definition of $\operatorname{pp}$ it holds that
$t_{1}(x)=t_{1}(y_{1})=\cdots=t_{1}(y_{k})$ or
$t_{2}(x)=t_{2}(y_{1})=\cdots=t_{2}(y_{k})$. In the first case, $t_{1}(x)\leq
0$ and since for at least one $z_{j}$ we have that $t_{1}(z_{j})\leq
t_{1}(x)$, it follows that $t_{3}(z_{j})\leq t_{3}(x)$. Otherwise, we have
that $t_{1}(x)>0$. Again, for at least one $z_{j}$ it holds that
$t_{2}(z_{j})\leq t_{2}(x)$. It follows that $t_{3}(z_{j})\leq t_{3}(x)$.
Thus, every clause of the form (1) is preserved by $\operatorname{pp}$.

We now show that every temporal relation $R$ preserved by $\operatorname{pp}$
may be defined as a conjunction of clauses of the desired form. Recall that
$\bigwedge\Phi_{R}^{m}$ defines $R$. We will obtain the desired definition of
$R$ by replacing every member $\phi$ of $\Phi_{R}^{m}$, which is of the form
(2), with a clause of the form (1). If $\phi$ is
$\neg(x=y_{1}\wedge\cdots\wedge y_{k-1}=y_{k})$, then we replace it by $(x\neq
y_{1}\vee\cdots\vee x\neq y_{k})$. Since these formulas are equivalent, the
transformation does not change the defined relation.

Otherwise, $\phi$ contains at least one occurrence of $<$ and hence we can
assume that $\phi$ is of the form:

$\neg(x=y_{1}\wedge\cdots\wedge y_{k-1}=y_{k}\wedge y_{k}<z_{1}\wedge
z_{1}\circ_{1}z_{2}\wedge\cdots\wedge z_{l-1}\circ_{l-1}z_{l}),$

where every $\circ_{i}$ is in $\\{=,<\\}$. Here we will consider two cases.
The first is where $R$ contains no tuple $t$ satisfying
$t(x)=t(y_{1})=\cdots=t(y_{k})<t(z_{i})$ for all $i\in[l]$. Observe that in
this case $R$ entails $\psi$ equal to $(x\neq y_{1}\vee\cdots\vee x\neq
y_{k}\vee x\geq z_{1}\vee\cdots\vee x\geq z_{l})$. It is easy to verify that
$\psi$ entails $\phi$. Hence, by Observation 3.1, it follows that we can
safely replace $\phi$ by $\psi$ in $\Phi^{m}_{R}$.

If $R$ contains a tuple $t$ satisfying
$t(x)=t(y_{1})=\cdots=t(y_{k})<t(z_{i})$ for all $i\in[l]$, then, as we show,
$R$ is not preserved by $\operatorname{pp}$. This leads to a contradiction
with the assumption. Consider a formula $\theta$ equal to
$\neg(z_{1}\circ_{1}z_{2}\wedge\cdots\wedge z_{l-1}\circ_{l-1}z_{l})$. We have
$\theta\preceq\phi$. Since $\phi$ is in $\Phi^{m}_{R}$, it follows that
$\theta$ is not in $\Phi_{R}$, and hence not entailed by $R$. It implies that
$R$ contains a tuple $t_{1}$ satisfying
$(z_{1}\circ_{1}z_{2}\wedge\cdots\wedge z_{l-1}\circ_{l-1}z_{l})$. Let
$\alpha$ be automorphisms of $({\mathbb{Q}};<)$ such that
$\alpha(t(x))<0<\alpha(t(z_{i}))$ for all $i\in[l]$. Then
$t_{2}=\operatorname{pp}(\alpha(t),t_{1})$ satisfies $\neg\phi$. Since $\phi$
is entailed by $R$, it follows $t_{2}\notin R$, and thus that $R$ is not
preserved by $\operatorname{pp}$. ∎

###  3.2. Characterization of $\min$-closed Relations

######  Theorem 3.3.

A temporal relation $R$ is preserved by $\min$ if and only if it can be
defined as a conjunction of clauses of the form

(3) $x\circ_{1}z_{1}\vee\cdots\vee x\circ_{l}z_{l},$

where for all $i\in[l]$, we have that $\circ_{i}$ is in $\\{\geq,>\\}$.

###### Proof.

Observe that to prove the left-to-right implication, it is enough to show that
every relation $R_{C}$ defined by a single clause $C$ of the form (3) is
preserved by $\min$. Let $t_{1},t_{2}$ be some tuples in $R$ and
$t_{3}=\min(t_{1},t_{2})$. Then $t_{1},t_{2}$ satisfy $x\circ_{i}z_{i}$, and
$x\circ_{j}z_{j}$ for some $i,j\in[l]$, respectively. We consider two cases.
Assume first that $t_{1}(z_{i})=t_{2}(z_{j})$. Here, it is easy to see that
$t_{3}(x)\geq t_{3}(z_{i})$ and $t_{3}(x)\geq t_{3}(z_{j})$. Thus if either
$\circ_{i}$ or $\circ_{j}$ is $\geq$, then we are done. Otherwise, it holds
that $t_{1}(x)>t_{1}(z_{i})$ and $t_{2}(x)>t_{2}(z_{j})$. It follows that
$t_{3}(x)$ is greater than both $t_{3}(z_{i})$ and $t_{3}(z_{j})$. This
settles the case where $t_{1}(z_{i})=t_{2}(z_{j})$. Assume now without loss of
generality that $t_{1}(z_{i})<t_{2}(z_{j})$. Observe that $t_{3}(z_{i})\leq
t_{3}(x)$. Thus we are done when $\circ_{i}$ is $\leq$. Otherwise we have that
$t_{1}(z_{i})<t_{1}(x)$ and that $t_{1}(z_{i})<t_{2}(z_{j})\leq t_{2}(x)$. It
follows that $t_{3}(z_{i})<t_{3}(x)$. It completes the proof of the left-to-
right implication.

We now turn to prove the reverse implication. Assume that there is some
relation $R$ preserved by $\min$ that cannot be defined by a conjunction of
clauses of the form (3). By Lemma 23 in [7], we have that every relation
preserved by $\min$ is also preserved by $\operatorname{pp}$. Hence, by
Theorem 3.2, the relation $R$ may be defined as a conjunction of clauses of
the form

(4) $x\neq y_{1}\vee\cdots\vee x\neq y_{k}\vee x\circ_{1}z_{1}\vee\cdots\vee
x\circ_{l}z_{l},$

where $\circ_{i}\in\\{>,\geq\\}$ for every $i\in[l]$. Consider the set of such
definitions of $R$ with a minimal number of disequalities and from this set
choose one with a minimal number of literals. Denote that formula by
$\phi_{R}$.

If $\phi_{R}$ does not have any disequalities, then we are done. Otherwise it
contains a clause $C$ of the form (4) with at least one disequality $(x\neq
y_{1})$. Since $\phi_{R}$ does not contain any unnecessary literals, there is
a tuple in $R$ that falsifies all literals in $C$ except for $(x\neq y_{1})$.
Suppose that $R$ contains both tuples $t_{1},t_{2}$ that falsify all literals
in $C$ except for $(x\neq y_{1})$ and satisfy $(x<y_{1})$ and $(x>y_{1})$,
respectively. Let $\alpha_{1}$ be an automorphism of $({\mathbb{Q}};<)$ that
sends $(t_{1}(x),t_{1}(y_{1}))$ to $(0,1)$, and $\alpha_{2}$ an automorphism
of $({\mathbb{Q}};<)$ that sends $(t_{2}(x),t_{2}(y_{1}))$ to $(1,0)$. Observe
that $t_{3}=\min(\alpha_{1}(t_{1}),\alpha_{2}(t_{2}))$ satisfies $(x=y_{1})$.
Since $\min$ preserves $=$, $\leq$, and $<$, we have that $t_{3}$ falsifies
all literals in $C$, hence we have a contradiction with the fact that $R$ is
preserved by $\min$. It follows that $R$ does not have either $t_{1}$ or
$t_{2}$. If $R$ does not contain $t_{1}$, then in $\phi_{R}$ we can replace
$C$ by $(x>y_{1}\vee x\neq y_{2}\vee\cdots\vee x\neq y_{k}\vee
x\circ_{1}z_{1}\vee\cdots\vee x\circ_{l}z_{l})$ obtaining a definition of $R$
guaranteed by Theorem 3.2 with a smaller number of disequalities. From now on
we can therefore assume that $R$ contains $t_{1}$.

Consider now the formula $\phi^{\prime}_{R}$ obtained from $\phi_{R}$ by
replacing the clause $C$ by the clause $C^{\prime}:=(y_{1}\neq x\vee y_{1}\neq
y_{2}\vee\cdots\vee y_{1}\neq y_{k}\vee y_{1}\circ_{1}z_{1}\vee\cdots\vee
y_{1}\circ_{l}z_{l})$. Observe that $C$ and $C^{\prime}$ entail each other.
Hence $\phi^{\prime}_{R}$ also defines $R$. Consider $C^{\prime}$ as a part of
$\phi^{\prime}_{R}$ and observe that no literal from $C^{\prime}$ can be
removed. Indeed, the new definition would have less disequlities or the same
number of disequalities and less literals than $\phi_{R}$. Thus $R$ contains a
tuple $t^{\prime}$ that satisfies all disjuncts of $C^{\prime}$ except for
$(y_{1}\neq x)$. As in the previous papragraph, we argue that $R$ cannot have
both tuples $t^{\prime}_{1}$, and $t^{\prime}_{2}$ that falsify all literals
in $C^{\prime}$ except for $(x\neq y_{1})$ and satisfy $(y_{1}<x)$ and
$(y_{1}>x)$, respectively. If $R$ does not contain $t^{\prime}_{1}$, then in
$\phi^{\prime}_{R}$ we can replace $C^{\prime}$ by $(y_{1}>x\vee y_{1}\neq
y_{2}\vee\cdots\vee y_{1}\neq y_{k}\vee y_{1}\circ_{1}z_{1}\vee\cdots\vee
y_{1}\circ_{l}z_{l})$ obtaining a definition of $R$ in the form guaranteed by
Theorem 3.2 with a smaller number of disequalities. Thus, we can assume that
$R$ contains $t^{\prime}_{1}$.

Now, suppose towards the contradiction that $R$ has both: $t_{1}$ that
falsifies all disjuncts of $C$ except for $(x\neq y_{1})$ and satisfies
$(x<y_{1})$; and $t^{\prime}_{1}$ that falsifies all disjuncts of $C^{\prime}$
except for $(y_{1}\neq x)$ and satisfies $(y_{1}<x)$. Let
$\alpha,\alpha^{\prime}$ be automorphisms of
$\operatorname{Aut}({\mathbb{Q}};<)$ such that $\alpha$ sends
$(t_{1}(x),t_{1}(y_{1}))$ to $(0,1)$ and $\alpha^{\prime}$ sends
$(t^{\prime}_{1}(x),t^{\prime}_{1}(y_{1}))$ to $(1,0)$. To complete the proof
we will show that $t_{4}=\min(\alpha(t_{1}),\alpha^{\prime}(t^{\prime}_{1}))$
falsifies all disjuncts of $C$. Since both $t_{1}$ and $t^{\prime}_{1}$ are in
$R$, we obtain a contradiction to the assumption that $R$ is preserved by
$\min$. Since
$\alpha(t_{1}(x))=\alpha(t_{1}(y_{2}))=\cdots=\alpha(t_{1}(y_{k}))=0$ and
$\alpha^{\prime}(t^{\prime}_{1}(y_{1}))=\alpha^{\prime}(t^{\prime}_{1}(y_{2}))=\cdots=\alpha^{\prime}(t^{\prime}_{1}(y_{k}))=0$,
it follows that $t_{4}(x)=t_{4}(y_{1})=\cdots=t_{4}(y_{k})=0$ and hence
$t_{4}$ falsifies all disequalities in $C$. Now, the clause $C$ contains a
disjunct $(x\circ_{i}z_{i})$ with $\circ_{i}\in\\{>,\geq\\}$ and $i\in[k]$ if
and only if $C^{\prime}$ contains $(y_{1}\circ_{i}z_{i})$. Assume that
$\circ_{i}$ is $>$. The same argument will work for $\geq$. Observe that
$\alpha(t_{1})$ satisfies $(x\leq z_{i})$ and sends $x$ to $0$; and that
$\alpha^{\prime}(t^{\prime}_{1})$ satisfies $(y_{1}\leq z_{i})$ and sends
$y_{1}$ to $0$. It follows that $t_{4}(x)\leq 0\leq t_{4}(z_{i})$. Thus
$t_{4}$ falsifies $(x<z_{i})$ and we are done. ∎

Example. According to Theorem 3.3, the relation $U$ from Section 2 can be
defined by a conjunction of clauses of the form 3. Indeed, observe that
$((x\geq y\vee x\geq z)\wedge y\geq x\wedge z\geq x)$ defines $U$.

###  3.3. Characterization of $\operatorname{mx}$-closed relations

Let us say that a boolean relation $S\subseteq\\{0,1\\}^{n}$ is _near-affine_
if it holds that $S\cup\\{(1,\ldots,1)\\}$ is preserved by the operation
$a(x,y)=x\oplus y\oplus 1$. Let us say that a formula $\phi$ is _min-affine_
if there exists a near-affine relation $T\subseteq\\{0,1\\}^{n}$ such that
$\phi$ is of the form

$\bigvee_{t\in
T}\big{(}(\bigwedge_{i,j:t_{i}=t_{j}=0}x_{i}=x_{j})\wedge(\bigwedge_{i,j:t_{i}=0,t_{j}=1}x_{i}<x_{j})\big{)}$

where $x_{1},\ldots,x_{n}$ are variables; here, the formula $\phi$ is intended
to be interpreted over the ordered rationals.

######  Theorem 3.4.

A temporal relation $R\subseteq{\mathbb{Q}}^{k}$ is preserved by
$\operatorname{mx}$ if and only if it is definable by a formula
$\phi(v_{1},\ldots,v_{k})$ that is the conjunction of min-affine formulas,
each of which is over a subset of $\\{v_{1},\ldots,v_{k}\\}$.

For a tuple $b=(b_{1},\ldots,b_{n})\in{\mathbb{Q}}^{n}$, we define the _min-
tuple_ of $b$ to be the tuple $t=(t_{1},\ldots,t_{n})\in\\{0,1\\}^{n}$ such
that $t_{i}=0$ if and only if $b_{i}$ is the minimum value in
$\\{b_{1},\ldots,b_{n}\\}$; note that the min-tuple of a ${\mathbb{Q}}$-tuple
of nontrivial arity always contains at least one entry equal to $0$. Observe
also that a tuple $b\in{\mathbb{Q}}^{n}$ is in the relation defined by a min-
affine formula if and only if the min-tuple of $b$ is in $T$.

We remark that we permit the empty conjunction of min-affine formulas, which
we consider to be true, and we also permit min-affine formulas where the near-
affine relation $T$ is empty, which formulas are considered to be false.

###### Proof.

For the right-to-left direction, it suffices to show that the claim holds in
the case that $\phi$ is defined by a single min-affine formula. So suppose
that $\phi$ is of the form described above, with respect to
$T\subseteq\\{0,1\\}^{n}$. Let $b=(b_{1},\ldots,b_{n})$,
$b^{\prime}=(b^{\prime}_{1},\ldots,b^{\prime}_{n})$ be two tuples in
${\mathbb{Q}}^{n}$ that satisfy $\phi$. Let $t,t^{\prime}\in T$ be the min-
tuples of $b,b^{\prime}$, respectively; so, $t,t^{\prime}$ witness that
$b,b^{\prime}$ satisfy $\phi$. Let $m,m^{\prime}$ denote the minimum values in
the tuples $b,b^{\prime}$, respectively.

We consider two cases.

Case $m=m^{\prime}$. If $t=t^{\prime}$, then the tuple
$\operatorname{mx}(b,b^{\prime})$ is witnessed to satisfy $\phi$ via the tuple
$t=t^{\prime}$; this can be verified by the definition of $\operatorname{mx}$.
If $t\neq t^{\prime}$, then we claim that the tuple
$\operatorname{mx}(b,b^{\prime})$ is witnessed to satisfy $\phi$ via the tuple
$t\oplus t^{\prime}\oplus 1$. First, observe that $t\oplus t^{\prime}\oplus 1$
is contained in $T\cup\\{(1,\ldots,1)\\}$ by the assumption that this relation
is preserved by the operation $a$; since $t\neq t^{\prime}$, it holds that
$t\oplus t^{\prime}\oplus 1$ is not equal to $(1,\ldots,1)$ and is thus
contained in $T$. Next, it is straightforwardly verified from the definition
of $\operatorname{mx}$ that $\operatorname{mx}(b,b^{\prime})$ takes on its
minimum value at exactly the coordinates where one of $b,b^{\prime}$ takes on
its minimum value and the other does not, which are precisely the coordinates
where $t\oplus t^{\prime}\oplus 1$ is equal to $0$.

Case $m\neq m^{\prime}$. We assume for the sake of notation that
$m<m^{\prime}$. In this case, the minimum entries among all entries in $b$ and
$b^{\prime}$ are the entries in $b$ that have value $m$. It follows from the
definition of $\operatorname{mx}$ that $\operatorname{mx}(b,b^{\prime})$ takes
on its minimum value at exactly the coordinates where $b$ does so, and hence
the tuple $\operatorname{mx}(b,b^{\prime})$ satisfies $\phi$ via the tuple
$t\in T$.

For the left-to-right direction, we proceed by induction on the arity $k$ of
the relation $R\subseteq{\mathbb{Q}}^{k}$. The case $k=0$ is verified as
follows: if $R$ is empty, then take the empty conjunction; if $R$ is non-
empty, then take the conjunction consisting of the single min-affine formula
on no variables with $T=\emptyset$. In what follows, we assume that $k>0$. Let
$\phi$ be the conjunction of all min-affine formulas that are entailed by
$R(v_{1},\ldots,v_{k})$. Suppose that $b=(b_{1},\ldots
b_{k})\in{\mathbb{Q}}^{k}$ satisfies $\phi$. Our goal is to show $b\in R$. Let
$t\in\\{0,1\\}^{k}$ be the min-tuple of $b$.

We claim that there is a tuple $c\in R$ with min-tuple $t$. Let
$T\in\\{0,1\\}^{k}$ be the set of min-tuples of tuples in $R$. It follows
directly from (Lemma 28 of [7]) that if $s,s^{\prime}\in T$, then $s\oplus
s^{\prime}\oplus 1\in T\cup\\{(1,\ldots,1)\\}$. From this implication, it is
straightforward to verify that $T$ is near-affine. Hence, the conjunction
$\phi$ contains as a conjunct a min-affine formula $\alpha$ with relation $T$.
Since $b$ satisfies $\alpha$, it follows that $t\in T$, from which the claim
follows.

If $t=(0,\ldots,0)$, then $c\in R$ and $b$ are both constant tuples. Since $b$
is equal to $c$ under an automorphism of $({\mathbb{Q}};<)$, we have $b\in R$.
So, we suppose that $t$ contains $1$ as an entry; for the sake of notation, we
assume that $t$ has the form $(1,\ldots,1,0,\ldots,0)$, where the first $m$
entries are $1$; here, $0<m<k$. We have that $(b_{1},\ldots,b_{m})$ satisfies
all min-affine formulas on variables from $v_{1},\ldots,v_{m}$ which are
entailed by $R(v_{1},\ldots,v_{k})$. Hence, by induction, it holds that
$(b_{1},\ldots,b_{m})\in\pi_{1,\ldots,m}R$, and that there exists a tuple of
the form $(b_{1},\ldots,b_{m},d)$ in $R$, where $d$ is a tuple of length
$(k-m)$. We can apply an automorphism to the tuple $(b_{1},\ldots,b_{m},d)$ to
obtain a tuple $(b^{\prime}_{1},\ldots,b^{\prime}_{m},d^{\prime})\in R$ where
all entries are positive. Also, by applying an automorphism to $c\in R$, we
can obtain a tuple of the form
$(c^{\prime}_{1},\ldots,c^{\prime}_{m},0,\ldots,0)$ where, for all coordinates
$i$ from $1$ to $m$, it holds that $c^{\prime}_{i}>b^{\prime}_{i}$. Applying
$\operatorname{mx}$ to the tuples
$(b^{\prime}_{1},\ldots,b^{\prime}_{m},d^{\prime})$ and
$(c^{\prime}_{1},\ldots,c^{\prime}_{m},0,\ldots,0)$, one obtains the tuple
$(\operatorname{mx}(b^{\prime}_{1},c^{\prime}_{1}),\ldots,\operatorname{mx}(b^{\prime}_{m},c^{\prime}_{m}),\operatorname{mx}(d^{\prime},\overline{0}))$,
where $\overline{0}$ is a tuple of length $(k-m)$ with all entries equal to
$0$, which is equivalent to $b$ under an automorphism. ∎

Example. Observe that the relation $X$ closed under $\operatorname{mx}$
presented in Section 2 is defined there as a conjunction of min-affine
formulas.

##  4\. Tractability Results

In this section, we prove the following theorem.

######  Theorem 4.1.

Let $\Gamma$ be a temporal constraint language preserved by an operation
$h\in\\{\operatorname{min},\operatorname{mx}\\}$. The problem
$\operatorname{QCSP}(\Gamma)$ is polynomial-time decidable.

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

$Q_{1}v_{1}\dots Q_{n}v_{n}(\psi_{1}\wedge\dots\wedge\psi_{m})$

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$.

######  Lemma 4.2.

Let $\Gamma$ be a temporal constraint language preserved by an operation
$h\in\\{\operatorname{min},\operatorname{mx}\\}$. Let
$\Phi(z_{1},\ldots,z_{m})=\forall y\exists x_{1}\ldots\exists x_{n}\phi$ be a
quantified constraint formula over $\Gamma$ having free variables
$\\{z_{1},\ldots,z_{m}\\}$. Let $\Phi^{\prime}(z_{1},\ldots,z_{m})$ be the
formula $\exists y\exists x_{1}\ldots\exists
x_{n}(\phi\wedge\bigwedge_{i\in[m]}(z_{i}<y))$. If the formula $\Phi$ is
satisfiable, then the formulas $\Phi$, $\Phi^{\prime}$ have the same
satisfying assignments over $\Gamma$.

###### Proof.

Observe that for every $q\in{\mathbb{Q}}$ there exists a value $\alpha(q)$
such that $h(q,p)=h(p,q)=\alpha(q)$ for all $p>q$. Notice that $\alpha(q)$ is
injective and preserves $<$.

Let $\Psi$ be the formula $\exists x_{1}\ldots\exists x_{n}\phi$ with free
variables $\\{z_{1},\ldots,z_{m},y\\}$. Assume that $\Phi$ is satisfiable;
then, there exists a tuple $(g_{1},\ldots,g_{m})\in{\mathbb{Q}}^{m}$ such
that, for all $d\in{\mathbb{Q}}$, the tuple $(g_{1},\ldots,g_{m},d)$ satisfies
$\Psi$. Clearly, all satisfying assignments of $\Phi$ are satisfying
assignments of $\Phi^{\prime}$. We thus need to show that each satisfying
assignment of $\Phi^{\prime}$ is a satisfying assignment of $\Phi$.

Let $(f_{1},\ldots,f_{m})\in{\mathbb{Q}}^{m}$ be a satisfying assignment of
$\Phi^{\prime}$. By the definitions of the formulas, there exists a value
$b\in{\mathbb{Q}}$ with $b>f_{i}$ for all $i\in[m]$ such that
$(f_{1},\ldots,f_{m},b)$ satisfies $\Psi$. By applying a suitable automorphism
to $(g_{1},\ldots,g_{m})$, we may assume that $f_{i}<g_{i}$ for all $i\in[m]$.
Now consider $h((f_{1},\ldots,f_{m},b),(g_{1},\ldots,g_{m},d))$ where
$d\in{\mathbb{Q}}$. In the first $m$ coordinates, this tuple is equal to
$(\alpha(f_{1}),\ldots,\alpha(f_{m}))$. In the last coordinate, this tuple is
equal to $h(b,d)$; by varying $d$, the value $h(b,d)$ can take on values from
every _orbit_ , where here we understand orbit to be with respect to the group
consisting of the automorphisms of $({\mathbb{Q}},<)$ that fix the values
$\alpha(f_{i})$. It follows that $(\alpha(f_{1}),\dots,\alpha(f_{m}))$
satisfies $\Phi$; since $\alpha^{-1}$ preserves all first-order definable
relations, we conclude that $(f_{1},\dots,f_{m})$ satisfies $\Phi$. ∎

With this lemma in hand, we now prove the theorem. Let $\Gamma$ be a structure
that is preserved by $\operatorname{min}$ or by $\operatorname{mx}$. We now
present an algorithm for $\operatorname{QCSP}(\Gamma)$. For the sake of
notation, we assume that the input instance is of the form $\forall
y_{1}\exists x_{1}\ldots\forall y_{n}\exists x_{n}\phi$, that is, it exhibits
a strict alternation between the two quantifier types. The result for the
general case can be obtained, for example, by considering an algorithm that
inserts dummy variables/quantifiers into an arbitrary instance of
$\operatorname{QCSP}(\Gamma)$ to massage it into the described form, and then
passes to the algorithm that we describe. We make use of the fact that
CSP$(\Gamma)$ can be decided by the algorithms given in [7]; indeed, those
algorithms describe how to compute satisfying assignments in the event that
they exist.

Algorithm for $\operatorname{QCSP}(\Gamma)$ where $\Gamma$ is preserved by
min/mx. Input: an instance $\forall y_{1}\exists x_{1}\ldots\forall
y_{n}\exists x_{n}\phi$ of $\operatorname{QCSP}(\Gamma)$. Set
$\Psi_{n}(y_{1},x_{1},\ldots,y_{n},x_{n})=\phi$. Loop $i=$ $n$ to $1$ Let
$\Phi_{i}=\forall y_{i}\exists x_{i}\Psi_{i}$ Let $\Phi^{\prime}_{i}$ be
$\exists y_{i}\exists x_{i}\big{(}\Psi_{i}\wedge(x_{1}<y_{i}\wedge\cdots\wedge
x_{i-1}<y_{i})\wedge(y_{1}<y_{i}\wedge\cdots\wedge y_{i-1}<y_{i}))$ If
$\Phi^{\prime}_{i}$ is satisfiable Let $w$ be a satisfying assignment Else
Return False If $w$ does not satisfy $\Phi_{i}$, Return False [Comment:
$\Phi_{i}$, $\Phi^{\prime}_{i}$ are equivalent and both satisfiable] Let
$\Psi_{i-1}=\Phi^{\prime}_{i}$ End Loop Return True

We now discuss the correctness of this algorithm. The algorithm maintains the
invariant that, at the beginning of each loop, the formula
$\Psi_{i}(y_{1},x_{1},\ldots,y_{i},x_{i})$ is equivalent to the formula
$\forall y_{i+1}\exists x_{i+1}\ldots\forall y_{n}\exists x_{n}\phi$. (By
equivalent, we mean that the formulas have the same satisfying assignments
over $\Gamma$.) This is certainly true for $i=n$ by the initialization of
$\Psi_{n}$.

We now consider the behavior of the algorithm for an execution of the loop. If
the formula $\Phi^{\prime}_{i}$ is not satisfiable, it follows that the
formula $\Phi_{i}$ is not satisfiable (as any satisfying assignment for
$\Phi_{i}$ is clearly one for $\Phi^{\prime}_{i}$), and hence that the
original sentence is false; the algorithm hence reports “False” correctly.

In the case that $\Phi^{\prime}_{i}$ is found to be satisfiable, consider
first the case that the satisfying assignment $w$ for $\Phi^{\prime}_{i}$ does
not satisfy $\Phi_{i}$. It follows by Lemma 4.2 that $\Phi_{i}$ is not
satisfiable, and hence that the original sentence is false; the algorithm
hence reports “False” correctly.

In the case that the assignment $w$ does satisfy $\Phi_{i}$, by Lemma 4.2, the
formulas $\Phi_{i}$, $\Phi^{\prime}_{i}$ are equivalent. Consequently, when
$\Psi_{i-1}$ is set equal to $\Phi^{\prime}_{i}$, by the definition of
$\Phi_{i}$ and the fact that the invariant held at the beginning of the loop,
the invariant will hold for the next execution of the loop. In the case that
$i=1$, if the loop does not return false, by the given argumentation, we have
that both $\Phi_{1}$ and $\Phi^{\prime}_{1}$ are true, and hence that the
original sentence is true.

##  5\. Discussion

The polynomial-time algorithms for the QCSP of temporal constraint languages
that are preserved by $\min$ or preserved by $\operatorname{mx}$ that we have
seen in this paper properly strengthen previously known algorithmic results
for the QCSP:

  * •

In [12], it has been shown that instances of the QCSP where all constraints
are of the form $x\geq y_{1}\vee\cdots\vee x\geq y_{k}$ can be solved in
polynomial time. All such constraints are preserved by $\min$ (this follows
immediately from the syntactic characterization that we gave for temporal
relations that are preserved by $\min$).

  * •

In [4], it has been shown that the QCSP for all temporal constraint languages
preserved by $\min$ is in NP.

There are (up to duality) two more temporal constraint languages whose CSP is
maximally tractable [7]. One of them is characterized by a certain binary
polymorphism called $\operatorname{ll}$. The tractability for the CSP for
$\operatorname{ll}$-closed languages has been shown in [8]. The QCSP for
$\operatorname{ll}$-closed languages is coNP-hard [6], so this is an instance
where maximal tractability doesn’t transfer to the QCSP. There is the temporal
constraint language that contains all relations preserved by the binary
operation $\operatorname{mi}$ (for a definition, see [7]). In this case, the
tractability of the QCSP is open. In fact, already the following is open.

######  Question 5.1.

Is $\operatorname{QCSP}(({\mathbb{Q}};\\{(x,y,z)\;|\;x=y\Rightarrow y\leq
z\\}))$ in P?

The relation defined by $x=y\Rightarrow y\leq z$ is indeed preserved by
$\operatorname{mi}$ (see [7]). Finally, the temporal languages preserved by a
constant operation have a tractable CSP [7]. As shown in previous work [12,
11], the QCSP for such languages may be contained in LOGSPACE, be NLOGSPACE-
complete, be P-complete, be NP-complete, or be PSPACE-complete.

Another field of open problems is related to the question how bad the
complexity of the QCSP becomes when we are outside the maximal tractable
classes. From maximal tractability of the CSP we only obtain NP-hardness, but
very often the problem might become even PSPACE-hard. Very often, questions in
this context lead to the following notorious open problem.

######  Question 5.2.

Is $\operatorname{QCSP}(({\mathbb{Q}};\\{(x,y,z)\;|\;x=y\Rightarrow y=z\\}))$
PSPACE-complete?

We only know that this QCSP is coNP-hard [6].

Postprint note: D. Zhuk and B. Martin solved Question 5.2 [22].

## References

  * [1] B. Aspvall, M. F. Plass, and R. E. Tarjan.  A linear-time algorithm for testing the truth of certain quantified boolean formulas.  Information Processing Letters, 8(3):121–123, 1979.
  * [2] L. Barto and M. Kozik.  Constraint satisfaction problems of bounded width.  In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), pages 595–603, 2009.
  * [3] M. Bodirsky.  Complexity classification in infinite-domain constraint satisfaction.  Memoire d’habilitation à diriger des recherches, Université Diderot – Paris 7. Available at arXiv:1201.0856, 2012.
  * [4] M. Bodirsky and H. Chen.  Collapsibility in infinite-domain quantified constraint satisfaction.  In Proceedings of Computer Science Logic (CSL), Szeged, Hungary, 2006.
  * [5] M. Bodirsky and H. Chen.  Relatively quantified constraint satisfaction.  Constraints, 14(1):3–15, 2009.
  * [6] M. Bodirsky and H. Chen.  Quantified equality constraints.  SIAM Journal on Computing, 39(8):3682–3699, 2010.  A preliminary version of the paper appeared in the proceedings of LICS’07.
  * [7] M. Bodirsky and J. Kára.  The complexity of temporal constraint satisfaction problems.  Journal of the ACM, 57(2):1–41, 2009.  An extended abstract appeared in the Proceedings of the Symposium on Theory of Computing (STOC’08).
  * [8] M. Bodirsky and J. Kára.  A fast algorithm and Datalog inexpressibility for temporal reasoning.  ACM Transactions on Computational Logic, 11(3), 2010.
  * [9] F. Börner, A. A. Bulatov, H. Chen, P. Jeavons, and A. A. Krokhin.  The complexity of constraint satisfaction games and QCSP.  Information and Computation, 207(9):923–944, 2009.
  * [10] P. J. Cameron.  The random graph.  R. L. Graham and J. Nešetřil, Editors, The Mathematics of Paul Erdös, 1996.
  * [11] W. Charatonik and M. Wrona.  Quantified positive temporal constraints.  In Proceedings of CSL, pages 94–108, 2008.
  * [12] W. Charatonik and M. Wrona.  Tractable quantified constraint satisfaction problems over positive temporal templates.  In LPAR, pages 543–557, 2008.
  * [13] H. Chen.  The computational complexity of quantified constraint satisfaction.  Ph.D. thesis, Cornell University, August 2004.
  * [14] H. Chen.  Meditations on quantified constraint satisfaction.  In Logic and Program Semantics - Essays Dedicated to Dexter Kozen on the Occasion of His 60th Birthday, Lecture Notes in Computer Science 7230. Springer, 2012.
  * [15] N. Creignou, S. Khanna, and M. Sudan.  Complexity Classifications of Boolean Constraint Satisfaction Problems.  SIAM Monographs on Discrete Mathematics and Applications 7, 2001.
  * [16] N. Creignou, P. G. Kolaitis, and H. Vollmer, editors.  Complexity of Constraints - An Overview of Current Research Themes [Result of a Dagstuhl Seminar], volume 5250 of Lecture Notes in Computer Science. Springer, 2008.
  * [17] T. Feder and M. Y. Vardi.  The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory.  SIAM Journal on Computing, 28:57–104, 1999.
  * [18] W. Hodges.  A shorter model theory.  Cambridge University Press, Cambridge, 1997.
  * [19] P. G. Jeavons and M. C. Cooper.  Tractable constraints on ordered domains.  Artificial Intelligence, 79(2):327–339, 1995.
  * [20] M. Karpinski, H. K. Büning, and P. H. Schmitt.  On the computational complexity of quantified Horn clauses.  In Proceedings of CSL, pages 129–137, 1987.
  * [21] D. Macpherson.  A survey of homogeneous structures.  Discrete Mathematics, 311(15):1599–1634, 2011.
  * [22] D. Zhuk and B. Martin.  The complete classification for quantified equality constraints.  CoRR, abs/2104.00406, 2021.