# Tractability Frontier for Dually-Closed Temporal Quantified Constraint
Satisfaction Problems

Michał Wrona  Theoretical Computer Science Department, Jagiellonian
University, Poland<EMAIL_ADDRESS>https://www.tcs.uj.edu.pl/wrona

###### Abstract.

A temporal (constraint) language is a relational structure with a first-order
definition in the rational numbers with the order. We study here the
complexity of the Quantified Constraint Satisfaction Problem (QCSP) for
temporal constraint languages.

Our main contribution is a dichotomy for the restricted class of dually-closed
temporal languages. We prove that QCSP for such a language is either solvable
in polynomial time or it is hard for NP or coNP. Our result generalizes a
similar dichotomy of QCSPs for equality languages [BC10], which are relational
structures definable by Boolean combinations of equalities.

Michał Wrona is partially supported by National Science Centre, Poland grant
number 2020/37/B/ST6/01179

##  1\. Introduction

The main goal of computational complexity is to characterize the difficulty of
decision problems by placing them into complexity classes according to the
time resources or space resources required to solve the problem. Much more
convenient and mathematically elegant, however, is to work with formalisms
such as Constraint Satisfaction Problems (CSPs) or Quantified Constraint
Satisfaction Problems (QCSPs), considered in this paper, that can express
infinitely many decision problems.

The formalism of Constraint Satisfaction Problems express Boolean
satisfiability problems: $3$-SAT, $2$-SAT; $k$-coloring and solving equations
over finite fields as well as many problems in different branches of
Artificial Intelligence such as Temporal Reasoning. An instance of the
Constraint Satisfaction Problem $\operatorname{CSP}(\Gamma)$ parametrized by a
relational structure $\Gamma$ is a primitive-positive (pp) sentence of the
form: $(\exists v_{1}\ldots\exists
v_{n}(R(v_{i_{1}},\ldots,v_{i_{k}})\wedge\ldots))$, where the inner
quantifier-free part is the conjunction of relational symbols, from the
signature of $\Gamma$, with variables.

This framework on one hand allows to define many important decision problems.
On the other hand, complexity classifications of the flavour of Schaefer’s
theorem [Sch78] these problems tend to display are of theoretical interest.
Directly relevant to this paper are temporal CSPs that are
$\operatorname{CSP}(\Gamma)$ for $\Gamma$ with a first-order definition in
$(\mathbb{Q};<)$, called _temporal (constraint) languages_. In [BK09], nine
large classes of tractable (solvable in polynomial time) temporal CSPs has
been identified and it was proved that all other such problems are NP-
complete. These nine tractable classes contain many decision problems studied
previously and scattered across the literature, e.g., the Betweenness and the
Cyclic Ordering Problem mentioned in [GJ78], and network satisfaction problem
for Point Algebra [VKvB89]. Furthermore, temporal $\operatorname{CSP}(\Gamma)$
has been studied in the literature for so-called Ord-Horn languages [NB95],
and AND/OR precedence constraints in scheduling [MSS04].

A natural generalization of the CSP is the Quantified Constraint Satisfaction
Problem (QCSP) for a relational structure $\Gamma$, denoted by
$\operatorname{QCSP}(\Gamma)$ that next to existential allows also universal
quantifiers in the input sentence. Similarly as the CSP, this problem has been
studied widely in the literature, see e.g. [BBJK03, Che12]. In this paper, we
study $\operatorname{QCSP}(\Gamma)$ for temporal languages. Although a number
of partial results has been obtained [BC10, ZM21, CM12, CW08b, CW08a, CW12,
CBW14, Wro14b], these efforts did not lead to a full complexity classification
of all temporal $\operatorname{QCSP}(\Gamma)$. One of the reasons is that
QCSPs are usually harder to classify than CSPs. This also holds in our case.
For instance, temporal CSPs are at most NP-complete, whereas temporal QCSPs
can be at most PSPACE-complete. In more detail, nine tractable classes of
temporal CSPs identified in [BK09] are given by so-called polymorphisms that
are in the case of temporal languages $\Gamma$ operations from
$\mathbb{Q}^{k}$ for some $k\in\mathbb{N}$ to $\mathbb{Q}$ that preserve
$\Gamma$ (homomorphisms from $\Gamma^{k}$ to $\Gamma$). The first of these
classes is the class preserved by constant operations, the other polymorphisms
(all binary) that come into play are named: $\min,\max,\text{mx},\text{dual-
mx},\text{mi},\text{dual-mi},\operatorname{ll},\operatorname{dual-ll}$.
Although constant polymorphisms make CSP trivial, QCSP for a temporal language
preserved by a constant polymorphism may be even PSPACE-complete [CW08a]. When
it comes to $\min,\max,\text{mx},\text{dual-mx}$, these operations provide
tractability for both temporal CSPs and QCSPs [CBW14], the complexity of
temporal QCSPs preserved by mi and dual-mi is not known. But it is known that
$\operatorname{ll}$ and $\operatorname{dual-ll}$ do not in general provide
tractability for temporal QCSPs [BC10, Wro14b]. However, Guarded Ord-Horn
Languages identified in [CW12], are all preserved by both $\operatorname{ll}$
and $\operatorname{dual-ll}$ and provide tractability for temporal QCSPs.
Other partial results obtained in the literature present somehow restricted
classifications of temporal QCSPs. Such classifications has been provided in
the following three cases.

  1. (1)

For a while it has been known [BC10] (see [CM12] for a different proof) that a
QCSP of an _equality language_ is in P, it is NP-complete or coNP-hard.
Recently the problem has been solved completely by showing that such a problem
is always either in LOGSPACE, it is NP-complete or PSPACE-complete [ZM21].

  2. (2)

_Positive languages_ that are relational structures with a positive definition
(first-order definition using $\wedge$, $\vee$, and $\leq$ only, negation is
not used) in $(\mathbb{Q};\leq)$ were classified in [CW08a, CW08b] where it
was proved that a corresponding QCSP is in LOGSPACE, is NLOGSPACE-complete,
P-complete, NP-complete or PSPACE-complete.

  3. (3)

A temporal language $\Gamma$ is dually-closed if in addition to a relation $R$
in $\Gamma$, it also contains a relation $-R$ obtained from $R$ by replacing
each tuple $t=(t[1],\ldots,t[n])$ with $-t=(-t[1],\ldots,-t[n])$ where $-$ is
a unary operation that sends a rational number $q$ to $-q$. A temporal
language is Ord-Horn if it can be defined by a conjunction of so-called Ord-
Horn clauses of the form: $(x_{1}\neq y_{1}\vee\cdots\vee x_{k}\neq y_{k}\vee
xRy)$ where $R\in\\{<,\leq,=\\}$ and both the disjunction of disequalities and
a literal $xRy$ can be omitted. It was proved in [Wro14b] that QCSP for a
dually-closed Ord-Horn language is in P if it is Guarded Ord-Horn and it is
coNP-hard otherwise.

The main contribution of this paper is the tractability frontier of QCSPs for
all dually-closed temporal languages. We prove that for every dually-closed
temporal language $\Gamma$ the problem $\operatorname{QCSP}(\Gamma)$ is either
in $P$ or it is NP-hard or coNP-hard. The result is built on all three
classifications listed above and clearly generalizes the third of the listed
classifications. It also generalizes the orginal result on equality languages
[BC10]: see Section 3 for details. Although our proof is based on previously
developed classifications, there are many interesting languages that are not
captured by any of them. For instance, the language
$(\mathbb{Q};\\{(x,y,z)\mid(x=y=z)\vee(x<y<z)\vee(x>y>z)\\},<)$, where $<$ is
a shortcut for $\\{(x,y)\in\mathbb{Q}^{2}\mid x<y\\}$, is dually-closed but
neither it is an equality language nor positive nor Ord-Horn.

To provide our classification we carry out a careful analysis of unary
operations preserving dually closed temporal languages. In particualar we
analyse operations that are non-injective. In the case of temporal CSPS, such
analysis is not necessary since all corresponding languages give rise to
trivial and therefore tractable problems. But it is not true not only for
temporal QCSPs but also for temporal abduction, whose complexity has been
investigated in [SW13, Wro14a]. Similar anylysis will be also helpful in order
to complete the project of identifying temporal languages with the so-called
local-to-global consistency, provided so far only for Ord-Horn languages
[Wro12].

###  1.1. Outline.

We start with preliminaries in Section 2. Partial results from the literature
that we use in this paper are presented in Section 3. In Section 4, we present
first some dually-closed temporal languages that give rise to hard QCSPs and
then we use these results to analyse dually-closed temporal languages that are
preserved by a constant operation. We show for corresponding QCSPs that either
one of the hard problems reduces to it or it is captured by one of the three
classifications listed above. In Section 5, we complete the classification of
QCSPs for dually closed temporal constraint languages.

##  2\. Preliminaries

We write $[n]$ for the set $\\{1,\ldots,n\\}$ with $n\in\mathbb{N}$ and
$t=(t[1],\ldots,t[n])$ for an $n$-ary tuple $t$. The $i$-th entry of the tuple
$t$, we denote by $t[i]$.

###  2.1. Formulas and definability.

We consider two restricted forms of first-order (fo)-formulas. Let $\tau$ be a
signature. A first-order $\tau$-formula is a _$\forall\\!\exists\\!\wedge$
-formula_ if it has the form $Q_{1}v_{1}\ldots
Q_{n}v_{n}(\psi_{1}\wedge\cdots\wedge\psi_{m})$, where each $Q_{i}$ is a
quantifier from $\\{\forall,\exists\\}$, and each $\psi_{i}$ is an atomic
$\tau$-formula of the form $R(x_{1},\ldots,x_{k})$ where $R\in\tau$. A
_primitive positive (pp)-formula_ is a $\forall\\!\exists\\!\wedge$-formula
where all quantifiers are existential. A _$\forall\\!\exists\\!\wedge$
-sentence (a pp-sentence)_ is a $\forall\\!\exists\\!\wedge$-formula (pp-
formula) without free variables.

We say that a relation $R$ is (fo)-definable ($\forall\\!\exists\\!\wedge$-,
or pp-definable) in a relational structure $\Gamma$ if $R$ has the same domain
as $\Gamma$, and there is a fo-formula ($\forall\\!\exists\\!\wedge$-, or pp-
formula) $\phi$ in the signature of $\Gamma$ such that $\phi$ holds exactly on
those tuples that are contained in $R$. A relational structure $\Delta$ is fo-
definable in $\Gamma$ if every relation in $\Delta$ is fo-definable in
$\Gamma$.

###  2.2. Temporal languages and formulas.

In this paper a _temporal formula_ is a fo-formula built from quantifiers,
logical connectivities and relational symbols: $<,\leq,\neq,=$. A _temporal
relation_ is a relation with a fo-definition in $(\mathbb{Q};<,\leq,\neq,=)$
and a _temporal (constraint) language_ is a relational structure over a finite
signature consisting of the domain $\mathbb{Q}$ and a finite number of
temporal relations.

###  2.3. QCSPs.

Let $\Gamma$ be a relational structure over a finite signature. The
_Quantified Constraint Satisfaction Problem_ for $\Gamma$, denoted by
$\operatorname{QCSP}(\Gamma)$, is the problem to decide if a given
$\forall\\!\exists\\!\wedge$-sentence over a signature of $\Gamma$ is true in
$\Gamma$.

######  Lemma 1.

([BC10, BBJK03]) Let $\Gamma_{1},\Gamma_{2}$ be constraint languages. If
$\Gamma_{1}$ has a $\forall\\!\exists\\!\wedge$-definition in $\Gamma_{2}$,
then $\operatorname{QCSP}(\Gamma_{1})$ is logarithmic space reducible to
$\operatorname{QCSP}(\Gamma_{2})$.

The above lemma states that we can reduce between QCSPs problems by providing
appropriate $\forall\\!\exists\\!\wedge$-definitions. In this paper we
restrict ourselves to pp-definitions but we rather work with their
characterization by polymorphisms than with them directly.

###  2.4. Polymorphisms.

Let $t_{1},\ldots,t_{k}$ be a $m$-tuples over $\mathbb{Q}$ and let $f$ be a
function (called also an operation) $f:D^{k}\rightarrow D$ Then we write
$f(t_{1},\ldots,t_{k})$ for the tuple obtained from the tuples
$t_{1},\ldots,t_{k}$ by applying $f$ componentwise, i.e., for the $m$-tuple
$t=(f(t_{1}[1],\ldots,t_{k}[1]),\ldots,f(t_{1}[m],\ldots,t_{k}[m]))$. If for
all $t_{1},\ldots,t_{k}\in R$ the tuple $t$ is also in $R$, then we say that
$f$ is a _polymorphism_ of (preserves) $R$. If it happens for all relations in
$\Gamma$, then $f$ is a polymorphism of (preserves) $\Gamma$. If $f$ does not
preserve $R$ or $\Gamma$, then we say that $f$ violates $R$ or $\Gamma$,
respectively.

Observe that an _automorphism_ is a unary polymorphism that preserves all
relations and their complements. The set of automorphisms of $\Gamma$ is
denoted by $Aut(\Gamma)$. An _oribt_ of a $k$-tuple $t$ wrt. $Aut(\Gamma)$ is
the set $\\{\alpha(t)\mid\alpha\in Aut(\Gamma)\\}$.

The set of all polymorphisms of a temporal language $\Gamma$, denoted by
$Pol(\Gamma)$, forms an algebraic object called a _clone_ [Sze86], which is a
set of operations defined on a set $\mathbb{Q}$ that is closed under
composition and that contains all projections. Moreover, $Pol(\Gamma)$ is also
closed under _interpolation_ (see Proposition 1.6 in [Sze86]): we say that a
$k$-ary operation f is _interpolated_ by a set of $k$-ary operations $F$ if
for every finite subset $A$ of $Q$ there is some operation $g\in F$ such that
$f(a)=g(a)$ for every $a\in A^{k}$ . We say that $F$ _locally generates_ an
operation $g$ if $g$ is in the smallest clone that is closed under
interpolation and contains all operations in $F$.

Since all temporal languages are preserved by all automorphisms of
$(\mathbb{Q};<)$, the following definition makes sense. We say that a set of
operations $F$ _generates_ an operation $g$ if $F$ together with all
automorphisms of $(\mathbb{Q};<)$ locally generates g. In case that $F$
contains just one operation $f$, we also say that $f$ generates $g$. We have
the following easy observation.

######  Observation 2.

Let $\Gamma$ be a temporal language. If $\Gamma$ is preserved by all
operations in $F$ and $F$ generates $g$, then $g$ also preserves $\Gamma$.

To prove that operations in $F$ generate $g$, we use the following result from
[BK09].

######  Lemma 3.

An operation $f$ generates $g$ if and only if every temporal relation that is
preserved by $f$ is also preserved by $g$.

For temporal languages we have the following chracterization of pp-
definability in terms of polymorphisms [BN06].

######  Theorem 4.

Let $\Gamma_{1},\Gamma_{2}$ be temporal languages, then $\Gamma_{2}$ has a pp-
definition in $\Gamma_{1}$ if and only if $Pol(\Gamma_{1})\subseteq
Pol(\Gamma_{2})$.

A direct consequence of Theorem 4 is that if a temporal language $\Gamma_{1}$
does not have a pp-definition in $\Gamma_{2}$, then there is an operation over
$\mathbb{Q}$ which is a polymorphism of $\Gamma_{2}$ but is not a polymorphism
of $\Gamma_{1}$. The next lemma [BK09] allows us to bound the arity of such
polymorphism.

######  Lemma 5.

Let $\Gamma$ be a relational structure and let $R$ be a $k$-ary relation that
is a union of $l$ orbits of $k$-tuples of $Aut(\Gamma)$. If $R$ is violated by
a polymorphism $g$ of $\Gamma$ of arity $m\geq l$, then $R$ is also violated
by an $l$-ary polymorphism of $\Gamma$.

Provided we have some more knowledge about $Pol(\Gamma)$, the following
observation allows us to reduce the arity of a considered polymorphism even
more.

######  Observation 6.

Let $t_{1},\ldots,t_{n},t\in\mathbb{Q}^{m}$. If $\Gamma$ is preserved by
$f:\mathbb{Q}^{n}\rightarrow\mathbb{Q}$ and
$g:\mathbb{Q}^{n-1}\rightarrow\mathbb{Q}$ such that $f(t_{1},\ldots,t_{n})=t$
and $g(t_{1},\ldots,t_{n-1})=t_{n}$ then $\Gamma$ is preserved by
$h(x_{1},\ldots,x_{n-1}):=f(x_{1},\ldots,x_{n-1},g(x_{1},\ldots,x_{n-1}))$
such that $h(t_{1},\ldots,t_{n-1})=t$.

###  2.5. Operations of Special Importance for this Paper.

Let $-:\mathbb{Q}\rightarrow\mathbb{Q}$ be the unary operation such that for
every $q\in\mathbb{Q}$ we have $-(q)=-q$. Let
$f:\mathbb{Q}^{n}\rightarrow\mathbb{Q}$. The _dual_ of $f$ is the operation
$-f(-x_{1},\ldots,-x_{n})$ denoted by $\overline{f}$.

Let $e$ be any order-preserving bijection between $(-\infty,\pi)$ and
$(\pi,\infty)$. Then the operation
$\operatorname{cyc}:\mathbb{Q}\rightarrow\mathbb{Q}$ is defined by $e(x)$ for
$x<\pi$ and by $e^{-1}(x)$ for $x>\pi$.

We say that $f:\mathbb{Q}^{k}\rightarrow\mathbb{Q}$ for some $k\in\mathbb{N}$
is a _constant operation_ if $f$ sends every $k$-tuple of rational numbers to
the same rational number.

We define the operation $\operatorname{wave}:\mathbb{Q}\rightarrow\mathbb{Q}$
to be equal to $-x$ for $x<0$, to $0$ for $0\leq x\leq 1$ and to $(x-1)$ for
$x>1$. We define the operation $\operatorname{peak}$ to be equal to $-1$ for
$x\neq 0$ and equal to $1$ for $x=0$. Further, we define
$\operatorname{su}_{i}:\mathbb{Q}\rightarrow\mathbb{Q}$ where $i\in\mathbb{N}$
to be an operation that satisfies $\operatorname{su}_{i}(x)=0$ for $x<0$;
$\operatorname{su}_{i}(x)=j$ for $[j-1,j)$ if $0<j<i$; and
$\operatorname{su}_{i}(x)=i$ for $[i-1,+\infty)$. We define
$\operatorname{ic}$ to be an operation such that $\operatorname{ic}(x)=x$ for
all $(x<0)$ and $\operatorname{ic}(x)=0$ for $(x\geq 0)$; and
$\operatorname{ci}$ to be an operation such that $\operatorname{ci}(x)=0$ for
$x<0$ and $\operatorname{ci}(x)=x$ for $(x\geq 0)$. Observe that
$\operatorname{ic}$ and $\operatorname{ci}$ are the duals of each other.

Let $\operatorname{pp}$ be an arbitrary binary operation on $\mathbb{Q}$ such
that $\operatorname{pp}(a_{1},b_{1})\leq\operatorname{pp}(a_{2},b_{2})$ if and
only if one of the following cases applies:

  * •

$a_{1}\leq 0$ and $a_{1}\leq a_{2}$

  * •

$0<a_{1}$, $0<a_{2}$, and $b_{1}\leq b_{2}$.

All operation that satisfy the above conditions generate each other and
therefore the same clone. The dual of $\operatorname{pp}$ is known as
$\operatorname{dual-pp}$.

Let $\operatorname{ll}$ be a binary operation on $Q$ such that
$\operatorname{ll}(a_{1},b_{1})<\operatorname{ll}(a_{2},b_{2})$ if

  * •

$a_{1}\leq 0$ and $a_{1}<a_{2}$, or

  * •

$a_{1}\leq 0$ and $a_{1}=a_{2}$ and $b_{1}<b_{2}$ , or

  * •

$a_{1},a_{2}>0$ and $b_{1}<b_{2}$, or

  * •

$a_{1}>0$ and $b_{1}=b_{1}$ and $a_{1}<a_{2}$.

All operations satisfying these conditions generate each other and the same
clone. The dual of $\operatorname{ll}$ is known as $\operatorname{dual-ll}$.

##  3\. Partial Classifications

In this section we present some results from the literature that we use for
our classification.

###  3.1. Equality Languages

We say that a temporal language $\Gamma$ is an _equality language_ if it is
definable by Boolean combinations of equalities ($=$). A temporal language is
an equality language if and only if $Pol(\Gamma)$ contains all permutations of
$\mathbb{Q}$, i.e., all bijunctive functions from $\mathbb{Q}$ to
$\mathbb{Q}$.

###  3.2. Dually-Closed Temporal Languages.

A temporal language $\Gamma$ is _dually-closed_ if $f\in Pol(\Gamma)$ always
whenever $\overline{f}\in Pol(\Gamma)$. Since $-$ is a permutation of
$\mathbb{Q}$, we have that it preserves every equality language and hence
every equality language is also dually-closed.

Let $R\subseteq\mathbb{Q}^{n}$. The dual of $R$ is the relation
$\\{(-t[1],\ldots,-t[n])\mid t\in R\\}$ denoted by $\overline{R}$. It is easy
to prove [Wro14b] that $\Gamma$ is a dually-closed language if and only if the
following holds: $\Gamma$ pp-defines $R$ if and only if it pp-defines
$\overline{R}$.

###  3.3. Ord-Horn and Guarded Ord-Horn Languages

Recall from the introduction that a temporal language is Ord-Horn if it can be
defined by a conjunction of Ord-Horn clauses of the form: $(x_{1}\neq
y_{1}\vee\cdots\vee x_{k}\neq y_{k}\vee xRy)$ where $R\in\\{<,\leq,=\\}$ and
both the disjunction of disequalities and a literal $xRy$ can be omitted. They
have the following algebraic characterization [Wro12].

######  Proposition 7.

Let $\Gamma$ be a temporal language. Then $\Gamma$ is Ord-Horn if and only if
it is preserved by both $\operatorname{ll}$ and $\operatorname{dual-ll}$.

The only tractable case for dually-closed $\operatorname{QCSP}(\Gamma)$ is
where $\Gamma$ is a guarded Ord-Horn language.

######  Definition 8.

We say that a temporal language $\Gamma$ is Guarded Ord-Horn (GOH) if every
relation in $\Gamma$ is definable by a GOH formula defined as follows.

  1. (1)

A Basic OH formula which is in one of the following forms is a GOH formula:

     * •

$x=y$, $x\leq y$,

     * •

$(x_{1}\neq y_{1}\vee\cdots\vee x_{p}\neq y_{p})$, or

     * •

$(x_{1}\neq x_{2}\vee\cdots\vee x_{1}\neq
x_{q})\vee(x_{1}<y_{1})\vee(y_{1}\neq y_{2}\vee\cdots\vee y_{1}\neq
y_{q^{\prime}})$.

  2. (2)

If $\psi_{1}$ and $\psi_{2}$ are GOH formulas, then $\psi_{1}\wedge\psi_{2}$
is a GOH formula.

  3. (3)

If $\psi$ is a GOH formula, then

$(x_{1}\leq y_{1})\wedge\ldots\wedge(x_{m}\leq y_{m})\wedge$

$(x_{1}\neq y_{1}\vee\ldots\vee x_{m}\neq y_{m}\vee\psi)$

is a GOH formula.

What might be interesting is that the algorithm for the following tractability
result uses local consistency methods.

######  Theorem 9.

([CW12]) Let $\Gamma$ be a GOH structure. Then $\operatorname{QCSP}(\Gamma)$
is solvable in polynomial time.

###  3.4. Dually-Closed Ord-Horn Languages

For temporal languages that are both dually-closed and Ord-Horn we have the
following dichotomy.

######  Theorem 10.

Let $\Gamma$ be a dually-closed Ord-Horn temporal language. Then
$\operatorname{QCSP}(\Gamma)$ is in P if $\Gamma$ is Guarded Ord-Horn.
Otherwise, it is coNP-hard.

###  3.5. Temporal Languages

We say that a temporal language is _positive_ if every relation in $\Gamma$
has a positive definition in $(\mathbb{Q};\leq)$, a first-order definition
with use of $\wedge,\vee$, and $\leq$ only. No negation is in use. The
following algebraic characterization of positive temporal languages is easy to
prove.

######  Proposition 11.

Let $\Gamma$ be a temporal language, then $\Gamma$ is positive if and only if
it is preserved by $\operatorname{wave}$.

The following dichotomy is a consequence of the classification in [CW08a,
CW08b].

######  Theorem 12.

Let $\Gamma$ be a positive temporal language. Then
$\operatorname{QCSP}(\Gamma)$ is in P if it is preserved either by
$\operatorname{pp}$ or $\operatorname{dual-pp}$. Otherwise it is NP-hard.

##  4\. Languages Preserved by a Constant Operation

First we present some temporal languages that give rise to coNP-hard and NP-
hard QCSPs.

######  Theorem 13.

Consider the following relations:

  * •

$\text{BetwC}=\\{(x,y,z)\in\mathbb{Q}^{3}\mid(x<y<z\vee x>y>z\vee x=y=z)\\}$;

  * •

$\text{CyclC}=\\{(x,y,z)\in\mathbb{Q}^{3}\mid(x<y<z\vee y<z<x\vee z<x<y\vee
x=y=z)\\}$;

  * •

$\text{EqXor}=\\{(x,y,z)\in\mathbb{Q}^{3}\mid(x=y\vee x=z)\\}$ ;

  * •

$\text{EqOr}_{n}=\\{(x_{1},\ldots,x_{n})\in\mathbb{Q}^{n}\mid(\bigvee_{i,j\in[n],i\neq
j}x_{i}=x_{j})\\}$;

  * •

$S=\\{(x,y,z)\in\mathbb{Q}^{3}\mid(x=y=z)\vee(x\neq y\wedge x\neq z\wedge
z\neq y)\\}$.

It holds that $\operatorname{QCSP}(\mathbb{Q};I)$;
$\operatorname{QCSP}(\mathbb{Q};S)$,
$\operatorname{QCSP}(\mathbb{Q};\text{BetwC})$ and
$\operatorname{QCSP}(\mathbb{Q};\text{CyclC})$ are coNP-hard; and
$\operatorname{QCSP}(\mathbb{Q};\text{EqXor})$ as well as
$\operatorname{QCSP}(\mathbb{Q};\text{EqOr}_{n})$ for all $n\geq 3$ are NP-
hard.

###### Proof.

To prove the theorem, we need one axiliary relation:
$I=\\{(x,y,z)\mid(x=y\rightarrow y=z)\\}$. By Theorem 5.5 in [BC10], it
follows that $\operatorname{QCSP}(I)$ and $\operatorname{QCSP}(S)$ are coNP-
hard as well as that EqXor and $\text{EqOr}_{n}$ for all $n\geq 3$ are NP-
hard. To prove that $\operatorname{QCSP}(\text{BetwC})$ and
$\operatorname{QCSP}(CyclC)$ are coNP-hard, we will show that they pp-define
$I$. Indeed, let $R\in\\{\text{BetwC},\text{CyclC}\\}$. We claim that
$I(x,y,z)=\exists u\exists v\leavevmode\nobreak\ (R(x,y,u)\wedge
R(x,y,v)\wedge R(u,v,z))$. In both cases, we have that if $x$ and $y$ have the
same value, then also $u$ and $v$ and in consequence also $z$ has the same
value. We have now to show that if $x$ has a different value than $y$, then
$z$ can have an arbitrary value.

We first consider the case where $x$ has the value less than $y$. If $R$ is
BetwC, then $u$ and $v$ have to be greater than $y$ and $u$ can be greater
than $v$, and hence $z$ can be greater than $y$, equal to $y$, between $x$ and
$y$, equal to $x$ as well as less than $x$. If $R$ is CyclC, then we can have
$x$ to be less than $y$ less than $u$ less than $v$ but still $z$ can be less
than $x$, equal to $x$, between $x$ and $y$, equal to $y$ as well as greater
than $y$.

The second case we consider is when $y$ has the value less than $x$. If $R$ is
BetwC then the analysis is symmetrical to that in the previous paragraph since
this relation is preserved by $-$. If $R$ is CyclC, then we can place $y,u$,
and $v$ so that $y<u<v<x$. Now, it is straighforward to check that $z$ can be
between $v$ and $x$, equal to $x$, greater than $x$, less than $y$, equal to
$y$ but also between $y$ and $u$. ∎

We will now show that if a dually-closed temporal constraint language is
preserved by a constant operation, then $\operatorname{QCSP}(\Gamma)$ pp-
defines one of relations in Theorem 13 and $\operatorname{QCSP}(\Gamma)$ is
hard, or $\Gamma$ is an equality language, a positive language or a dually-
closed Ord-Horn language. We start with an auxiliary lemma.

######  Lemma 14.

Let $f:\mathbb{Q}\rightarrow\mathbb{Q}$ be an operation that is neither
constant nor it preserves $<$, then one of the following holds.

  1. (1)

The operation $f$ is injective and then:

    1. (a)

$f$ preserves $\text{Betw}=\\{(x,y,z)\in\mathbb{Q}^{3}\mid(x<y<z\vee
x>y>z)\\}$ and generates $-$; or

    2. (b)

$f$ preserves $\text{Cycl}=\\{(x,y,z)\in\mathbb{Q}^{3}\mid(x<y<z\vee y<z<x\vee
z<x<y)\\}$ and generates $\operatorname{cyc}$; or

    3. (c)

$f$ preserves
$\text{Sep}=\\{(x_{1},y_{1},x_{2},y_{2})\in\mathbb{Q}^{4}\mid(x_{1}<x_{2}<y_{1}<y_{2})\vee(x_{1}<y_{2}<y_{1}<x_{2})\vee(y_{1}<x_{2}<x_{1}<y_{2})\vee(y_{1}<y_{2}<x_{1}<x_{2})\vee(x_{2}<x_{1}<y_{2}<y_{1})\vee(x_{2}<y_{1}<y_{2}<x_{1})\vee(y_{2}<x_{1}<x_{2}<y_{1})\vee(y_{2}<y_{1}<x_{2}<x_{1})\\}$
and generates both $-$ and $\operatorname{cyc}$; or

    4. (d)

$f$ generates all permutations.

  2. (2)

The operation $f$ is of infinite image but is not injective and then generates
$\operatorname{ci}$ or $\operatorname{ic}$.

  3. (3)

The operation $f$ is of finite image and then it generates
$\operatorname{su}_{1}$ or $\operatorname{peak}$.

###### Proof.

The proof consists of three parts which correspond to three items from the
formulation of the lemma.

(Part One) If $f$ is injective, then by the arguments in the proofs of
Propositions 17 and 19 in [BK09], it is generated by automorphisms of
$(\mathbb{Q};<)$. Since $f$ does not preserve $<$, by Cameron’s theorem
[Cam76] (see also Theorems 4 and 13 in [BK09]), we have that one of the items
in Case 1 holds.

(Part Two) We now turn to the case where $f$ is of infinite image but is not
injective. Before we continue, we make an observation.

######  Observation 15.

Let $f:\mathbb{Q}\rightarrow\mathbb{Q}$ be an operation that takes infinitely
many values in $(a,b)$ where $a,b\in\mathbb{Q}\cup\\{-\infty,+\infty\\}$, then
there is an infinite sequence of rational numbers contained in $(a,b)$:

  1. (1)

either of the form $q_{1}>q_{2}>\cdots$ such that:

    1. (a)

$f(q_{1})>f(q_{2})>\cdots$,

    2. (b)

$f(q_{1})<f(q_{2})<\cdots$;

  2. (2)

or of the form $q_{1}<q_{2}<\cdots$ such that:

    1. (a)

$f(q_{1})>f(q_{2})>\cdots$,

    2. (b)

$f(q_{1})<f(q_{2})<\cdots$;

###### Proof.

Let $S$ be the set of elements in $(a,b)$ such that for all $x,y\in(a,b)$ we
have $f(x)\neq f(y)$ and let $c\in S$. Now, either $S_{1}:=S\cap(a,c)$ or
$S_{2}:=S\cap(c,b)$. We consider only the second case in which we have that
either for every $q\in S_{2}$ there is $p>q$ and we are in Case 2; or there is
$p\in S_{2}$ such that for every $\delta>0$, there is $q\in S_{2}$ such that
$p<q$ and $\left|p-q\right|\leq\delta$ and we are in Case 1. Now an easy
application of Infinite Ramsey Theorem gives us subsequence which is either
strictly increasing or strictly decreasing.

We now show that in Cases 1b and 2a, the operation $f$ generates $-$. We
convey the proof only in the second case. We use Lemma 3. Let $t$ be an
$n$-ary tuple (of some $n$-ary relation) such that $p_{1}<\ldots<p_{k}$ are
all pairwise different values in $t$. It is enough to observe that
$-(t)=\beta(f(\alpha(t)))$ where $\alpha,\beta\in Aut(Q;<)$ are such that
$\alpha$ sends $p_{1},\ldots,p_{k}$ to $q_{1},\ldots,q_{k}$ and $\beta$ sends
$f(q_{1}),\ldots,f(q_{k})$ to $-(p_{1}),\ldots,-(p_{k})$. ∎

Let now $f$ be a non injective function that takes infinitely many values for
arguments in the interval $(a_{1},a_{2})$ with
$a_{1},a_{2}\in\mathbb{Q}\cup\\{-\infty,\infty\\}$. Then we are in one of the
four cases of Observation 15. To simplify the proof, we will always assume
that we are either in Case 2b or in Case 2a. The proofs for two other cases
are always similar.

Since $f$ is non-injective, there are $c_{1}<c_{2}$ such that
$f(c_{1})=f(c_{2})$. Furthermore, $f$ takes infinitely many values either for
arguments less than $a_{1}$, or arguments greater than $a_{1}$. In the first
case there are infinitely many values taken above $f(a_{1})$ or below
$f(a_{1})$. By the previous assumptions, we are either in Case 2b or Case 2a.
In the second case $f$ generates $-$. In any case, either by considering
$g:=f$ or $g:=-f$, we have one of the two following situations. In the first
situation, there is a sequence of rational numbers
$q_{1}<q_{2}<\cdots<c_{1}<c_{2}$ such that
$g(q_{1})<g(q_{2})<\cdots<g(c_{1})=g(c_{2})$. In the second situation there is
a sequence of rational numbers $q_{1}<q_{2}<\cdots<c_{1}<c_{2}$ such that
$g(c_{1})=g(c_{2})<g(q_{1})<g(q_{2})<\cdots$. In both situations the operation
$g$ generates $\operatorname{ic}$. We provide the proof only for the first
one. We use Lemma 3. Let $t$ be a tuple of length $n$ in some relation $R$
with pairwise different values $p_{1}<\ldots<p_{k}<0\leq
p_{k+1}<\cdots<p_{k+l}$ We prove that $\operatorname{ic}(t)$ is in $R$ by the
induction on $l$. If $l=0$, then $\operatorname{ic}(t)=\alpha(t)$ where
$\alpha\in Aut(\mathbb{Q};<)$ is the identity on $\mathbb{Q}$. Assume now that
we are done for $l=m$. We will prove the claim for $l=(m+1)$. Let $t$ be a
tuple in $R$ with pairwise different values $p_{1}<\cdots<p_{k}<0\leq
p_{k+1}<\cdots<p_{k+m+1}$ and $\alpha\in Aut(Q;<)$ such that
$\alpha(p_{1})<\cdots<\alpha(p_{k})<\alpha(p_{k+1})<0\leq\alpha(p_{k+2})<\cdots<\alpha(p_{k+m+1})$.
By the induction hypothesis, the relation $R$ contains a tuple
$t_{1}=\operatorname{ic}(\alpha(t))$ with values
$r_{1}<\cdots<r_{k}<r_{k+1}<r_{k+2}=0$, where for all $i\in[k+1]$ we have
$r_{i}=\operatorname{ic}(\alpha(p_{i}))$ and
$r_{k+2}=\operatorname{ic}(\alpha(p_{k+2}))=\cdots=\operatorname{ic}(\alpha(p_{k+m+1}))=0$.
Let now $\beta\in Aut(\mathbb{Q};<)$ be such that for $i\in[k]$ it holds
$\beta(r_{i})=q_{i}$ and $\beta(r_{k+1})=c_{1}$ and $\beta(r_{k+2})=c_{2}$,
and $\gamma\in Aut(\mathbb{Q};<)$ be such that for all $i\in[k]$ we have
$\gamma(g(q_{i}))=p_{i}$ as well as $\gamma(g(c_{1}))=\gamma(g(c_{2}))=0$.
Observe that $\gamma(g(t_{1}))$ is equal to $\operatorname{ic}(t)$. It follows
that $R$ contains $\operatorname{ic}(t)$ and we are done.

From now on, we assume that $f$ takes finitely many values for arguments in
the interval $(-\infty,c_{1})$ and infinitely in the interval
$(c_{1},\infty)$. Again, we consider only Cases 2b and 2a from Observation 15.
In the first situation we look at $g:=f$ and in the second situation we look
at $g:=-f$. In any case we have either a sequence of rational numbers
$d_{1}<d_{2}<c_{1}<q_{1}<q_{2}<\cdots$ such that either
$g(d_{1})=g(d_{2})<g(q_{1})<g(q_{2})<\cdots$ or
$g(q_{1})<g(q_{2})<\cdots<g(d_{1})=g(d_{2})$. In both cases we have that $g$
generates $\operatorname{ci}$. The proof is similar to the proof that $g$
generates $\operatorname{ic}$ from the previous paragraph. This completes the
second part of the proof of the lemma.

(Part Three) If $f$ is of finite image, then either there are two intervals
$[a_{1},a_{2}]$ and $[a_{3},a_{4}]$ with $a_{1}<a_{2}<a_{3}<a_{4}$ as well as
$b_{1}\neq b_{2}$ such that for all $x\in[a_{1},a_{2}]$ we have $f(x)=b_{1}$
and for all $x\in[a_{3},a_{4}]$ it holds $f(x)=f(y)=b_{2}$ or almost all
rational numbers are sent by $f$ to the same value. We will show that in the
first case, the operation $f$ generates $\operatorname{su}_{1}$, whereas in
the second case it generates $\operatorname{peak}$. We start with first case.
Observe that without loss of generality we can assume that $b_{1}<b_{2}$.
Indeed, if $b_{1}>b_{2}$, then instead of $f$ we consider $g=f(\alpha(f))$
where $\alpha\in Aut(\mathbb{Q};<)$ satisfies $\alpha(b_{1})=a_{3}$ and
$\alpha(b_{2})=a_{1}$. The operation $g$ satisfies $g(x)=a_{1}$ for all
$x\in[a_{1},a_{2}]$ and $g(x)=a_{3}$ for all $x\in[a_{3},a_{4}]$. By Lemma 3,
it is enough to show that every relation preserved by $f$ is also preserved by
$\operatorname{su}$. Let $R$ be any relation preserved by $f$ and $t$ a tuple
in $R$. We have to show that $t_{1}=\operatorname{su}(t)$ is also a tuple in
$R$. Let $q_{1},\ldots,q_{k}<0\leq q_{k+1}<\cdots<q_{l}$ be pairwise different
values occurring in $t$; $\alpha\in Aut(\mathbb{Q}:<)$ such that $\alpha$
sends $q_{1},\ldots,q_{k}$ to an interval $[a_{1},a_{2}]$ and
$q_{k+1},\ldots,q_{l}$ to $[a_{3},a_{4}]$ and $\beta\in Aut(\mathbb{Q}:<)$
such that $\beta(b_{1})=0$ and $\beta(b_{2})=1$. Observe that
$\beta(\operatorname{su}(\alpha(t)))=t_{1}$. It follows that $f$ generates
$\operatorname{su}_{1}$.

We now consider the case where $f$ sends almost all values to $b$. Since $f$
is not a constant operation, there is $a_{1}\in\mathbb{Q}$ such that
$f(a_{1})=b_{1}\neq b$. Again, without loss of generality we can assume that
$b<b_{1}$. If it is not the case, then instead of $f$ we consider
$f(\alpha(f))$ where $\alpha\in Aut(Q;<)$ satisfies $\alpha(b_{1})=a$ and
$\alpha(b)=a_{1}$ for some $a<a_{1}$ with $f(a)=b$. Let now $R$ be a relation
preserved by $f$ and $t\in R$, by Lemma 3, we have to show that
$\operatorname{peak}(t)$ is in $R$. Let
$q_{1},\ldots,q_{k},q_{k+1},\ldots,q_{l}$ be pairwise different values in $t$
different than $0$ and such that $q_{1}<\cdots<q_{k}<0<q_{k+1}<\cdots<q_{l}$.
Let $\alpha\in Aut(Q;\leq)$ be such that it sends $q_{1},\ldots,q_{k}$ to
rational numbers less than $a_{1}$ such that
$f(\alpha(q_{1}))=\cdots=f(\alpha(q_{k}))=b$, it sends $0$ to $a_{1}$ and
$q_{k+1},\ldots,q_{l}$ to rational numbers greater than $a_{1}$ such that
$f(\alpha(q_{k+1}))=\cdots=f(\alpha(q_{l}))=b$. Further, let $\beta\in
Aut(Q;\leq)$ satisfy $\beta(b)=-1$ and $\beta(b_{1})=1$. Observe that
$\beta(f(\alpha(t)))=\operatorname{peak}(t)$. It follows that $f$ generates
$\operatorname{peak}$. ∎

Now, we make a first serious step. We show that either $\Gamma$ pp-defines
BetwC, which by Theorem 13 gives rise to the hard $\operatorname{QCSP}$ or
$\Gamma$ is preserved by one of few polymorphisms.

######  Lemma 16.

Let $\Gamma$ be a temporal language preserved by a constant operation. If
$\Gamma$ does not pp-define BetwC, then $\Gamma$ is preserved by
$\operatorname{ll},\operatorname{dual-ll},\operatorname{pp}$ or
$\operatorname{dual-pp}$, $\operatorname{su}_{1}$,$\operatorname{peak}$,
$\operatorname{ic}$, $\operatorname{ci}$, $-$, $\operatorname{cyc}$ or all
permutations.

###### Proof.

If $\Gamma$ does not pp-define BetwC, then by Theorem 4, it follows that there
is an operation $f$ that preserves $\Gamma$ and violates BetwC. By Lemma 5, we
can assume that $f$ is a ternary operation such that for tuples
$t_{1},t_{2},t_{3}$ satisfying $t_{1}[1]<t_{1}[2]<t_{1}[3]$,
$t_{2}[1]>t_{2}[2]>t_{2}[3]$ and $t_{3}[1]=t_{3}[2]=t_{3}[3]$ we have
$f(t_{1},t_{2},t_{3})=t$ and $t\notin\text{BetwC}$. Since $\Gamma$ is
preserved by a constant operation, it is preserved by all constant operations,
in particular some constant operation $g$ satisfying $g(t_{1},t_{2})=t_{3}$.
By Observation 6, we have that $\Gamma$ is preserved by an operation
$h:\mathbb{Q}^{2}\rightarrow\mathbb{Q}$ such that $h(t_{1},t_{2})=t$.

Observe that the operation $h$ violates Betw defined in the formulation of
Lemma 14. If $h$ preserves $<$, then by Lemma 49 in [BK09], we have that $g$
generates $\operatorname{pp}$, $\operatorname{dual-pp}$, $\operatorname{ll}$,
or $\operatorname{dual-ll}$. From now on, we assume that $h$ violates $<$. We
now consider the situation where $h$ violates $\leq$. If it is the case, then
there are tuples $s_{1},s_{2}$ such that $s_{1}[1]<s_{1}[2]$,
$s_{2}[1]=s_{2}[2]$, and such that for $s=h(s_{1},s_{2})$ we have $s[1]>s[2]$.
Since $\Gamma$ is preserved by a constant operation we can again apply
Observation 6 and obtain that there is a unary operation $h_{s}$ preserving
$\Gamma$ such that $h_{s}(s_{1})=s$. Since $h_{s}$ is neither a constant
operation nor it preserves $<$, it follows by Lemma 14 that $h_{s}$ generates
$\operatorname{su}_{1},\operatorname{peak},\operatorname{ic},\operatorname{ci},-,\operatorname{cyc}$
or all permutations. From now on we assume that $h$ preserves $\leq$. Let
$h_{i}:=h(x,x)$. If $h_{i}$ is neither a constant operation nor it preserves
$<$, then we are again done by Lemma 14. Thus, we have two cases to consider
to complete the proof.

First we look at the situation where $h_{i}$ is a constant operation that
sends all the rational numbers to $a$. Since $t\notin\text{BetwC}$, there are
$i\neq j$ in $[3]$ such that $t[i]\neq t[j]$. It follows that either $t[i]$ or
$t[j]$ is different than $a$. Assume without loss o generality that
$t[i]=b\neq a$. Let $d_{1},d_{2}\in\mathbb{Q}$ be such that
$d_{1}<\min(t_{i}[1],t_{i}[2])<d_{2}$ and $\alpha\in Aut(\mathbb{Q};<)$ be
such that it sends all rational numbers
$q\in(-\infty,d_{1})\cup(d_{2},\infty)$ to $q$; the interval
$[d_{1},t_{i}[2])$ to $[d_{1},t_{i}[1])$, and $[t_{i}[2],d_{2}]$ to
$[t_{i}[1],d_{2}]$. Due to Cantor’s theorem such $\alpha$ clearly exists.
Consider $h_{a}(x)=h(x,\alpha(x))$. Observe that there is an infinite sequence
$q_{1}<q_{2}<\cdots<t_{i}[1]<p_{1}<p_{2}<\cdots$ of rational numbers such that
$h_{a}(q_{1})=h_{a}(q_{2})=\cdots=h_{a}(p_{1})=h_{a}(p_{2})=\cdots=a$ and
$h(t_{i})=b$. Now as in the second paragraph of the third part of the proof of
Lemma 14, we can show that $h_{a}$ and in consequence $f$ generates
$\operatorname{peak}$.

The last case to consider is where $h_{i}$ preserves $<$. Since $h$ violates
$<$ and preserves $\leq$, there are $c_{1},c_{2}\in\mathbb{Q}^{2}$ such that
$c_{1}[i]<c_{2}[i]$ for $i\in[2]$ and $f(c_{1})=f(c_{2})$. Let
$d_{1},d_{2}\in\mathbb{Q}^{2}$ be such that
$d_{1}<\min(c_{1}[1],c_{1}[2])<\max(c_{2}[1],c_{2}[2])<d_{2}$ and $\alpha\in
Aut(\mathbb{Q};<)$ be such that it sends all rational numbers
$q\in(-\infty,d_{1})\cup(d_{2},\infty)$ to $q$; the interval
$[d_{1},c_{2}[1])$ to $[d_{1},c_{1}[1])$; the interval $[c_{2}[1],c_{2}[2])$
to $[c_{1}[1],c_{1}[2])$; the interval $[c_{2}[2],d_{2}]$ to
$[c_{2}[1],d_{2}]$. Such $\alpha$ clearly exists. Consider
$h_{a}(x)=h(x,\alpha(x))$. Since $h_{a}$ is not injective and not constant, it
follows by Lemma 14 that $h_{a}$ and in consequence $f$ generates
$\operatorname{peak},\operatorname{su}_{1},\operatorname{ic},\operatorname{ci},-,\operatorname{cyc}$,
or all permutations. ∎

From now on, we provide lemmas which takes care of polymorphisms listed in
Lemma 16. We show that in each of these cases, we can reduce our
classification to the existing ones. We first take a look at the situation
where $\Gamma$ is preserved by $\operatorname{ll},\operatorname{dual-
ll},\operatorname{pp}$ or $\operatorname{dual-pp}$.

######  Lemma 17.

Let $\Gamma$ be a dually-closed temporal language such that $\Gamma$ is
preserved by $\operatorname{pp},\operatorname{dual-pp},\operatorname{ll},$ or
$\operatorname{dual-ll}$. Then $\Gamma$ is a dually-closed Ord-Horn constraint
language.

###### Proof.

Since $\Gamma$ is dually-closed, we have two cases to consider. If $\Gamma$ is
preserve by $\operatorname{ll}$ or $\operatorname{dual-ll}$, then it is
preserved by the both operations. It follows by Proposition 7, then $\Gamma$
is an Ord-Horn language.

It remains to consider the case where $\Gamma$ is preserved by both
$\operatorname{pp}$ and $\operatorname{dual-pp}$. By [CBW14], if $Pol(\Gamma)$
contains $\operatorname{pp}$ then every $R$ in $\Gamma$ 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}.$

The language $\Gamma$ is also preserved by $\operatorname{dual-pp}$. In that
case as we show every clause 1 in the definition of every relation in $\Gamma$
satisfies $l=1$. Suppose not. Then there is $R$ in $\Gamma$ that does not have
an Ord-Horn definition. Let $\phi$ be a definition of $R$ in terms of clauses
of the form (1) with a minimal number of literals and let $\psi$ be clause in
$\phi$ for which $l\geq 2$. By the minimality of $\phi$, it is satisfied by
assignments $t_{1},t_{2}:Var(\phi)\rightarrow\mathbb{Q}$ such that $t_{i}$
violates all literals in $\psi$ except for $x\geq z_{i}$. Let $\alpha_{1}\in
Aut(\mathbb{Q};<)$ be such that
$\alpha_{1}(t_{1}(z_{1}))\leq\alpha_{1}(t_{1}(x))\leq
0<\alpha_{1}(t_{1}(z_{2}))$. To reach the contradiction, we will show that
$f:=\operatorname{dual-pp}(\alpha_{1}(t_{1}),t_{2})$ does not satisfy any
disjunct of $\psi$. By the definition of $\operatorname{dual-pp}$, it follows
that $f(x)<f(z_{1})$ and $f(x)<f(z_{2})$. All other literals are violated
since $\operatorname{dual-pp}$ preserves $<$ and $=$. It completes the proof
of the lemma. ∎

The operations $\operatorname{ic}$ and $\operatorname{ci}$ are the duals to
each other and as we show in the proof of Theorem 23,
$\\{\operatorname{ic},\operatorname{ci}\\}$ generates $\operatorname{su}_{1}$.
Since we restrict ourselves to dually-closed languages, the next lemma applies
also to the case where $\Gamma$ is preserved by $\operatorname{ic}$ or
$\operatorname{ci}$.

######  Lemma 18.

Let $\Gamma$ be an operation preserved by $\operatorname{su}_{1}$, then
$\Gamma$ is positive or $\operatorname{QCSP}(\Gamma)$ is NP-hard.

###### Proof.

We first consider the case where $\Gamma$ is preserved by all
$\operatorname{su}_{i}$ with $i\in\mathbb{N}$. In this case, as we show,
$\Gamma$ is a positive language. To this end, we have to show that
$\\{\operatorname{su}_{i}\mid i\in\mathbb{N}\\}$ generate
$\operatorname{wave}$. Let $t$ be an $n$-tuple with pairwise different values
$q_{1}<\cdots<q_{a}<0\leq q_{a+1}<\cdots<q_{a+b}\leq
1<q_{a+b+1}<\cdots<q_{a+b+c}$. Let $\alpha\in Aut(\mathbb{Q};<)$ be such that
it sends $q_{i}$ for $i\in[a]$ to $i-1$, $q_{i}$ for $i\in\\{a+1,\ldots,b\\}$
to the interval $[a,a+1)$ and $q_{i}$ for $i\in\\{b+1,\ldots,c\\}$ to $a+i$
and $\beta$ such that it sends $\operatorname{su}_{n}(\alpha(q_{i}))$ for
$i\in[a]$ to $q_{i}$; $\operatorname{su}_{n}(\alpha(q_{a+1}))$ to $0$ and
$\operatorname{su}_{n}(\alpha(q_{a+b+i}))$ for $i\in[c]$ to $(q_{a+b+i}-1)$.
Observe that $\beta(\operatorname{su}_{n}(\alpha(t)))=\operatorname{wave}(t)$.

The second case holds if there exists $k\in\mathbb{N}$ such that $\Gamma$ is
preserved by $\operatorname{su}_{k}$ but is not preserved by
$\operatorname{su}_{k+1}$. Let $R\in\Gamma$ and $t\in R$ such that
$t_{s}=\operatorname{su}_{k+1}(t)$ is not in $R$. For the sake of simplicity
assume that $t$ is an injective tuple, that is, all its entries are pairwise
different. Observe that $t$ has to be of length $n>(k+1)$. Let
$\Pi_{1},\ldots,\Pi_{k+1}$ be a partition of $[n]$ such that $i,j\in\Pi_{a}$
for $a\in[l]$ if and only if $t_{s}[i]=t_{s}[j]$. Consider the relation
$R_{s}$ pp-defined by
$R(x_{1},\ldots,x_{n})\wedge\bigwedge_{a\in[k+1]}\bigwedge_{i,j\in\Pi_{a}}x_{i}=x_{j}$.
Intuitively, $R_{s}$ is just $R$ where coordinates from the same $\Pi_{i}$ are
identified. Since $R$ and also $R_{s}$ are preserved by
$\operatorname{su}_{k}$ and $R_{s}$ is of arity $k+1$, it is easy to see that
$R_{s}$ is preserved by $\operatorname{wave}$ and hence it is a positive
relation. By Theorem 12, it follows that a positive relation $R$ gives rise to
NP-hard QCSP unless it is preserved by $\operatorname{pp}$ or
$\operatorname{dual-pp}$. We now show that $R_{s}$ is preserved by none of
these operations, which imply that $\operatorname{QCSP}(\mathbb{Q};R_{s})$ and
hence $\operatorname{QCSP}(\Gamma)$ is NP-hard and completes the proof of the
lemma. Since $t$ is in $R$ and $R$ is preserved by $\operatorname{su}_{k}$, it
follows that $R$ contains also both $t_{1}$ such that
$t_{1}[\Pi_{1}]<t_{1}[\Pi_{2}\cup\Pi_{3}]<\cdots<t[\Pi_{k+1}]$ and $t_{2}$
such that $t_{2}[\Pi_{1}\cup\Pi_{2}]<t[\Pi_{3}]<\cdots<t[\Pi_{k+1}]$.
[NOTATION: We write $t[S]$ where $S\subseteq[n]$ for the value $t[i]$ that is
common for all $i\in S$.] By the pp-definition, we have that $R_{s}$ contains
tuples $t_{1}^{s}$ and $t_{2}^{s}$ such that
$t_{1}^{s}[1]<t_{1}^{s}[2]=t_{1}^{s}[3]<\cdots<t_{1}^{s}[k+1]$ and
$t_{2}^{s}[1]=t_{2}^{s}[2]<t_{2}^{s}[3]<\cdots<t_{2}^{s}[k+1]$. Let now
$\alpha\in Aut(\mathbb{Q};<)$ be such that
$\alpha(t_{1}^{s}[1])<0<\alpha(t_{1}^{s}[2])$. Observe now that
$t_{3}^{s}=\operatorname{pp}(\alpha(t_{1}^{s}),t_{2}^{s}))$ satisfies
$t_{3}^{s}[1]<t_{3}^{s}[2]<t_{3}^{s}[3]<\cdots<t_{3}^{s}[k+1]$. Hence there is
$\beta\in Aut(\mathbb{Q};<)$ such that $\beta(t_{3}^{s})=t^{s}$. It
contradicts the fact that $t^{s}$ is not in $R$. It follows that $R_{s}$ is
not preserved by $\operatorname{pp}$. To show that the relation is not
preserved by $\operatorname{dual-pp}$, we proceed in the similar way with the
difference that we take $\alpha$ such that
$\alpha(t_{2}^{s}[1])<0<\alpha(t_{2}^{s}[2])$ and
$t_{3}^{s}=\operatorname{pp}(\alpha(t_{2}^{s}),t_{1}^{s}))$. ∎

The next case to consider is where $\Gamma$ is preserved by
$\operatorname{peak}$.

######  Lemma 19.

Let $\Gamma$ be a temporal language preserved by $\operatorname{peak}$. If
$\Gamma$ defines neither EqXor nor $\text{EqOr}_{n}$ for any $n\geq 3$, then
$\Gamma$ is preserved by all permutations.

###### Proof.

We need some definitions. Let $n$ be a natural number, $t$ an $n$-ary tuple
and $S\subseteq[n]$. If for all $i,j\in S$, we have $t[i]=t[j]$, then we write
$t[S]$ to indicate the value which is common for all $t[i]$ with $i\in S$. We
say that an $n$-ary tuple $t$ is an _ordered $k$-partition_ of $[n]$ if there
is an underlying partition $\\{\Pi_{1},\ldots,\Pi_{k}\\}$ of $[n]$ such that
for all $i,j\in[n]$ we have $t[i]=t[j]$ if and only if $i,j\in\Pi_{l}$ for
some $l\in[k]$ and $t[\Pi_{i}]<t[\Pi_{i+1}]$ for all $i\in[k-1]$. Let
$t_{1},t_{2}$ be two ordered $k$-partitions of $[n]$ with the same underlying
partition $\\{\Pi_{1},\ldots,\Pi_{k}\\}$ of $[n]$. Then there is an
automorphism $\alpha\in Aut(\mathbb{Q};<)$ such that $t_{1}=\alpha(t_{2})$.
Hence for an $n$-ary relation $R$, we have $t_{1}\in R$ if and only if
$t_{2}\in R$. We will write $t[\Pi_{1}]<\cdots<t[\Pi_{k}]$ for an ordered
$k$-partition of $[n]$ with an underlying partition
$\\{\Pi_{1},\ldots,\Pi_{k}\\}$ of $[n]$. We also a need a special treatment of
ordered $2$-partitions. We say that a tuple $t$ is an $[a,b]$ $2$-partition if
$\left|\Pi_{1}\right|=a$ and $\left|\Pi_{2}\right|=b$.

If $\Gamma$ pp-defines neither EqXor nor $\text{EqOr}_{n}$ for any $n\geq 3$,
then there are operations $f_{x}$ and $f_{1},f_{2},\ldots$ preserving $R$ such
that $f_{x}$ violates EqXor while $f_{n}$ for $n\geq 3$ violates
$\text{EqOr}_{n}$. Let $R$ be an $n$-ary relation and $t$ a tuple in $R$. For
the sake of simplicity we assume that the values in $t$ are pairwise
different. To show that all permutation of $t_{o}$ are in $R$ we will prove
that for all $k\leq n$, the relation $R$ contains all ordered $k$-partitions
of $n$.

#### First Part of the Proof.

In the first part of the proof, we prove that $R$ contains all $2$-partitions
of $n$. By induction on $m=\min(a,b)-1$ we show that every $[a,b]$
$2$-partition of $[n]$ is in $R$. If $m=0$, then $a=1$ or $b=1$. In this case
we just use the operation $\operatorname{peak}$ and automorphisms of
$Aut(\mathbb{Q};<)$. Indeed, let $t[[n]\setminus\\{i\\}]<t[\\{i\\}]$ be an
ordered $[n-1,1]$ $2$-partition of $[n]$. Observe that $t$ is equal to
$\beta(\operatorname{peak}(\alpha(s)))$ where $\alpha,\beta$ are automorphisms
of $(\mathbb{Q};<)$ such that $\alpha$ sends $s[i]$ to $0$; and $\beta$ sends
$-1$ and $1$ to $t[[n]\setminus\\{i\\}]$ and $t[\\{i\\}]$, respectively. Now
from $t[[n]\setminus\\{i\\}]<t[\\{i\\}]$ we can obtain any $[1,n-1]$
$2$-partition of $[n]$ by first sending $t[[n]\setminus\\{i\\}]$ and
$t[\\{i\\}]$ to $0$ and $1$, respectively, it flips the values; and then by
using an appropriate automorphism of $(\mathbb{Q};<)$. Assume now that we are
done for $[a,b]$ $2$-partitions with $m$, as defined above, equal to $l$. We
will now prove that the claim holds for $l+1$. By the observation above, we
have that $R$ is preserved by $f_{x}$. Since $f_{x}$ violates EqXor, by
Theorem 4 and Lemma 5, there are tuples $s,s_{1},s_{2},s_{3},s_{4},s_{5}$ such
that

  * •

$s_{1}[1]=s_{1}[2]=s_{1}[3]$,

  * •

$s_{2}[1]=s_{2}[2]<s_{2}[3]$,

  * •

$s_{3}[1]=s_{3}[2]>s_{3}[3]$,

  * •

$s_{4}[1]=s_{4}[3]<s_{4}[2]$,

  * •

$s_{5}[1]=s_{5}[3]>s_{5}[2]$.

and we have $f(s_{1},s_{2},s_{3},s_{4},s_{5})=s$ and $s$ such that $s[1]\neq
s[2]$ and $s[1]\neq s[3]$.

Let $t_{g}[\Pi_{1}]<t_{g}[\Pi_{2}]$ be any ordered $[n-l-1,l+1]$ ordered
$2$-partition of $[n]$. Let $i\in\Pi_{i}$. Since $R$ is preserved by a
constant operation we have that it contains a tuple $t_{1}$ such that all its
entries are equal to $s_{1}[1]$. Moreover, by the induction assumption, we
have that $R$ contains all of the following:

  * •

an ordered $[n-l,l]$ $2$-partition
$t_{2}[\Pi_{1}\cup\\{i\\}]=s_{1}[1]<t_{2}[\Pi_{2}\setminus\\{i\\}]=s_{1}[3]$;

  * •

an ordered $[l,n-l]$ $2$-partition
$t_{3}[\Pi_{2}\setminus\\{i\\}]=s_{2}[3]<t_{3}[\Pi_{1}\cup\\{i\\}]=s_{2}[1]$;

  * •

an ordered $[n-1,1]$ $2$-partition
$t_{4}[[n]\setminus\\{i\\}]=s_{4}[1]<t_{4}[i]=s_{4}[2]$; and

  * •

an ordered $[1,n-1]$ $2$-partition
$t_{5}[i]=s_{5}[2]<t_{5}[[n]\setminus\\{i\\}]=s_{5}[1]$.

It is now straigthforward to check that $t=f(t_{1},t_{2},t_{3},t_{4},t_{5})$
satisfies $t[\Pi_{1}]\neq t[\Pi_{2}\setminus\\{i\\}]$ and $t[\Pi_{1}]\neq
t[\\{i\\}]$. It is now easy to see that by applying $\operatorname{peak}$ and
appropriate automorphisms of $(\mathbb{Q};<)$ we can obtain
$t_{g}[\Pi_{1}]<t_{g}[\Pi_{2}]$. This proves that we can obtain any
$[n-l-1,l+1]$ ordered $2$-partition of $[n]$. Any $[l+1,n-l-1]$ ordered $2$
partition of $[n]$ can be obtained from a corresponding $[n-l-1,l+1]$ ordered
partition just by flipping the values. This can be obtained with the use of
$\operatorname{peak}$. This proves that $R$ contains all ordered $[a,b]$
$2$-partitions where $\min(a,b)=l+1$ and completes the induction step. By
mathematical induction we obtain that $R$ contains all ordered $2$-partitions.

#### Second Part of The Proof.

Here we show that $R$ contains all ordered $k$-partitions of $[n]$ for $k\leq
n$. By the previous part of the proof we have that $R$ contains all
$2$-partition of $n$, which we will use as a base case in our induction.
Assume now that we are done for $k=l$. We will now prove the claim for
$k=l+1$. Recall that $f_{l+1}$ is an operation preserving $\Gamma$ and
violating $\text{EqOr}_{l+1}$. Let $s_{1},\ldots,s_{p}$ be a list of all, up
to isomorphisms, different, ordered $a$-partition of $[l+1]$ with $a\leq l$.
Observe that up to a permutation of $s_{1},\ldots,s_{p}$, we can assume that
$f(s_{1},\ldots,s_{p})=s$ and $s$ satisfies $s[1]<\cdots<s[l+1]$. Let now
$t_{g}[\Pi_{1}]<\cdots<t_{g}[\Pi_{l+1}]$ be any ordered $(l+1)$-partition of
$[n]$. We will now show that $t_{g}$ is in $R$. Let $t_{1},\ldots,t_{p}$ be a
list of all, up to isomorphisms, ordered $a$-partitions of $[n]$ with $a\leq
l$ such that for all $b\in[p]$ and $i\in[l+1]$ we have
$t_{b}[i]=s_{b}[\Pi_{i}]$. By the induction hypothesis we have that all tuples
$t_{1},\ldots,t_{p}$ are in $R$. Observe that there is an automorphism
$\alpha\in Aut(\mathbb{Q};<)$ such that $\alpha(f(t_{1},\ldots,t_{p}))=t_{g}$.
This completes the induction step. By mathematical induction we have that
every ordered $k$-partition with $k\leq n$ is in $R$. This completes the proof
of the lemma. ∎

The only remaining polymorphisms from Lemma 16 are $-$ and
$\operatorname{cyc}$. We take care of them in three steps. First we look at
the case where $\Gamma$ has only $-$ out of these two.

######  Lemma 20.

Let $\Gamma$ be a temporal language preserved by a constant operation and by
$-$. If $\Gamma$ does not pp-define BetwC, then it is preserved by
$\operatorname{su},\operatorname{peak},\operatorname{ci},\operatorname{ic},\operatorname{cyc}$
or all permutations.

###### Proof.

If $\Gamma$ does not pp-define BetwC, then by Theorem 4, there is an operation
$f_{b}$ that preserves $\Gamma$ and violates BetwC. By Lemma 5, we can assume
that $f_{b}$ is a ternary operation such that for some tuples
$t_{1},t_{2},t_{3}$ satisfying $t_{1}[1]<t_{1}[2]<t_{1}[3]$,
$t_{2}[3]<t_{2}[2]<t_{2}[1]$, and $t_{4}[1]=t_{4}[2]=t_{4}[3]$ we have
$f_{b}(t_{1},t_{2},t_{3})=t$ and $t\notin\text{BetwC}$. Since $\Gamma$ is
preserved by a constant operation, it is preserved by all constant operations,
in particular some constant operation $f_{c}$ satisfying
$f_{c}(t_{1},t_{2},t_{3})=t_{4}$. By Observation 6, we have that $\Gamma$ is
preserved by an operation $f_{d}:\mathbb{Q}^{3}\rightarrow\mathbb{Q}$ such
that $f_{d}(t_{1},t_{2})=t$. There are also an automorphism $\alpha\in
Aut(\mathbb{Q};<)$ such that $\operatorname{cyc}(\alpha(t_{1}))=t_{2}$ and
$\operatorname{cyc}(\alpha(t_{1}))=t_{3}$. Thus, by applying Observation 6
again, we conclude that $\Gamma$ is preserved by a unary operation $f$ such
that $f(t_{1})=t$. Observe that the operation $f$ violates Betw and $<$ and is
not a constant operation. We us Lemma 14. First we consider the case where $f$
is injective. Since it violates both Betw and $<$, we have by Item 1 that $f$
generates $\operatorname{cyc}$ or all permutations. On the other hand, if $f$
is not injective, then it generates
$\operatorname{ic},\operatorname{ci},\operatorname{su}_{1}$, or
$\operatorname{peak}$. It completes the proof of the lemma. ∎

We now take care of the situation where $\Gamma$ is preserved by
$\operatorname{cyc}$.

######  Lemma 21.

Let $\Gamma$ be a temporal language preserved by a constant operation and by
$\operatorname{cyc}$. If $\Gamma$ does not pp-define CyclC, then it is
preserved by
$\operatorname{su}_{1},\operatorname{peak},\operatorname{ci},\operatorname{ic},-$
or all permutations.

###### Proof.

If $\Gamma$ does not pp-define CyclC, then by Theorem 4, it follows that there
is an operation $f_{b}$ that preserves $\Gamma$ and violates CyclC. By Lemma
5, we can assume that $f_{b}$ is an operation of arity four such that some for
tuples $t_{1},t_{2},t_{3},t_{4}$ satisfying $t_{1}[1]<t_{1}[2]<t_{1}[3]$,
$t_{2}[2]<t_{2}[3]<t_{2}[1]$, $t_{3}[3]<t_{3}[1]<t_{3}[2]$, and
$t_{4}[1]=t_{4}[2]=t_{4}[3]$ we have $f_{b}(t_{1},t_{2},t_{3},t_{4})=t$ and
$t\notin\text{BetwC}$. Since $\Gamma$ is preserved by a constant operation, it
is preserved by all constant operations, in particular some constant operation
$f_{c}$ satisfying $f_{c}(t_{1},t_{2},t_{3})=t_{4}$. By Observation 6, we have
that $\Gamma$ is preserved by an operation
$f_{d}:\mathbb{Q}^{3}\rightarrow\mathbb{Q}$ such that
$f_{d}(t_{1},t_{2},t_{3})=t$. There are also automorphisms $\alpha,\beta\in
Aut(\mathbb{Q};<)$ such that $\operatorname{cyc}(\alpha(t_{1}))=t_{2}$ and
$\operatorname{cyc}(\alpha(t_{1}))=t_{3}$. Thus, by applying Observation 6
twice, we conclude that $\Gamma$ is preserved by a unary operation $f$ such
that $f(t_{1})=t$. Observe that $f$ violates $<$ and Cycl, defined in the
formulation of Lemma 14. If $f$ is injective, then by Item 1 of Lemma 14, we
have that $f$ generates $-$ or all permutations. The operation $f$ is also not
constant. Thus, if it is not injective, then by the same lemma, it follows
that it generates $\operatorname{ic},\operatorname{ci},\operatorname{su}_{1}$
or $\operatorname{peak}$. This completes the proof of the lemma. ∎

Finally, we consider the situation where $\Gamma$ is preserved by both $-$ and
$\operatorname{cyc}$.

######  Lemma 22.

Let $\Gamma$ be a temporal language preserved by a constant operation by $-$,
and $\operatorname{cyc}$. If $\Gamma$ does not pp-define $S$, then it is
preserved by
$\operatorname{su},\operatorname{peak},\operatorname{ci},\operatorname{ic}$ or
all permutations.

###### Proof.

The proof goes along the lines of the proof of Lemmas 20 and 21. Again, if
$\Gamma$ does not pp-define $S$, then there is an operation $f_{b}$ that
preserves $\Gamma$ and violates $S$. Again, we can assume that the arity of
$f_{b}$ is the number of orbits of $3$-tuples with respect to
$Aut(\mathbb{Q};<)$ contained in $S$. Thus there are tuples
$t_{1},t_{2},t_{3},t_{4},t_{5},t_{6},t_{7}$ such that
$t_{1}[1]<t_{1}[2]<t_{1}[3]$, $t_{2}[1]<t_{2}[3]<t_{1}[2]$,
$t_{3}[2]<t_{3}[1]<t_{3}[3]$, $t_{4}[2]<t_{4}[3]<t_{4}[1]$,
$t_{5}[3]<t_{5}[1]<t_{5}[2]$, $t_{6}[3]<t_{6}[2]<t_{6}[1]$, and
$t_{7}[1]=t_{7}[2]=t_{7}[3]$. Observe that tuples $t_{2},\ldots,t_{7}$ can be
obtained from $t_{1}$ by applying to $t_{1}$ the operations:
$-.\operatorname{cyc}$, constant operations and automorphisms of
$(\mathbb{Q};<)$. Thus by multiple application of Observation 6, we conclude
that there is a unary operation $f$ that preserves $\Gamma$ and such that
$f(t_{1})=t$ for some $t\notin S$. Observe that $f$ violates
$<,\text{Betw},\text{Cycl}$ and is not a constant operation. If it is
injective, then by Item 1 of Lemma 14, it follows that $f$ generates all
permutations. If $f$ is not injective, then by the same lemma, we have that
$f$ generates $\operatorname{ic},\operatorname{ci},\operatorname{su}_{1}$ or
$\operatorname{peak}$. ∎

We can use the above lemmas to prove the following.

######  Theorem 23.

Let $\Gamma$ be a dually-closed temporal constraint language preserved by a
constant operation, then one of the following holds.

  1. (1)

The problem $\operatorname{QCSP}(\Gamma)$ is coNP-hard or NP-hard.

  2. (2)

$\Gamma$ is a dually-closed Ord-Horn constraint language.

  3. (3)

$\Gamma$ is a positive constraint language.

  4. (4)

$\Gamma$ is an equality constraint language.

###### Proof.

By Lemma 16, we have that either $\Gamma$ pp-defines BetwC and then by Theorem
13, the problem $\operatorname{QCSP}(\Gamma)$ is coNP-hard; or $\Gamma$ is
preserved by one of the following operations:
$\operatorname{pp},\operatorname{dual-
pp},\operatorname{ll},\operatorname{dual-
ll},\operatorname{su}_{1},\operatorname{ic},\operatorname{ci},\operatorname{peak},-,\operatorname{cyc}$,
or all permutations. If it is one of the first four operations, then by Lemma
17 we have that $\Gamma$ is a dually-closed Ord-Horn language and we are in
case 2.

Observe now that a dually-closed language preserved by $\operatorname{ic}$ or
$\operatorname{ci}$ is preserved by both $\operatorname{ic}$ and
$\operatorname{ci}$. These operations are the dual of each other. Moreover,
$\\{\operatorname{ic},\operatorname{ci}\\}$ generate $\operatorname{su}_{1}$.
Indeed, for every tuple $t$ with pairwise different values
$q_{1}<\cdots<q_{a}\leq 0<q_{a+1}<\cdots<q_{a+b}$ we have that
$\operatorname{ci}(\alpha(\operatorname{ic}(t)))=\operatorname{su}_{1}(t)$
where $\alpha$ is an automorphism of $(\mathbb{Q};<)$ such that
$\alpha(q_{1})<\cdots<\alpha(q_{a})<0$ and $\alpha(O)=1$. It follows by Lemma
18, that if a dually-closed temporal constraint language $\Gamma$ preserved by
$\operatorname{su}_{1},\operatorname{ic}$, or $\operatorname{ci}$, then
$\Gamma$ is either hard and we are in Case 1 or positive and we are in Case 3.
Further, by Lemma 19 and Theorem 13, if $\Gamma$ is preserved by
$\operatorname{peak}$, then $\Gamma$ is either hard and we are in Case 1 or
$\Gamma$ is an equality language and we are in case 4. What remained to
consider is the situation where $\Gamma$ is preserved by $-$ or
$\operatorname{cyc}$. In the former case we use Lemma 20 and Lemma 21 in the
latter. We have that either $\Gamma$ pp-defines a relation that give rise to
hard $\operatorname{QCSP}$ or it is preserved by both $-$ and
$\operatorname{cyc}$. In the first case we are in Case 1 and we are done,
whereas in the second we use Lemma 22. Here, again, either $\Gamma$ pp-defines
$S$ and by Theorem 13, we are in Case 1; or one of the previously considered
cases holds and we are also done. This completes the proof of the theorem. ∎

##  5\. Classification

Here, we prove that $\operatorname{QCSP}(\Gamma)$ for a dually-closed temporal
language $\Gamma$ is either hard or it is in $P$.

######  Theorem 24.

Let $\Gamma$ be a dually-closed temporal language. Then $\Gamma$ is a Guarded
Ord-Horn language and $\operatorname{QCSP}(\Gamma)$ is in P. Otherwise
$\operatorname{QCSP}(\Gamma)$ is NP-hard or coNP-hard.

###### Proof.

By Theorem 50 in [BK09], it follows that $\operatorname{CSP}(\Gamma)$, and
hence also $\operatorname{QCSP}(\Gamma)$ is hard, or $\Gamma$ is preserved by:
$\operatorname{pp},\operatorname{dual-
pp},\operatorname{ll},\operatorname{dual-ll}$ or a constant operation. In
first four cases we use Lemma 17 which reduces the problem to the
classification of dually-closed Ord-Horn temporal constraint satisfaction
problems. In the case where $\Gamma$ is preserved by a constant operation, by
Theorem 23, $\operatorname{QCSP}(\Gamma)$ is hard or $\Gamma$ is either a
dually-closed Ord-Horn language or an equality language, or a positive
language. In the first two cases, it is in fact dually-closed Ord-Horn and
hence by Theorem 10, the language $\Gamma$ is Guarded Ord Horn and
$\operatorname{QCSP}(\Gamma)$ is in $P$ or $\operatorname{QCSP}(\Gamma)$ is
coNP-hard. We now consider the case where $\Gamma$ is positive. By Theorem 12,
we have that either $\operatorname{QCSP}(\Gamma)$ is NP-hard, or $\Gamma$ is
preserved by $\operatorname{pp}$ or $\operatorname{dual-pp}$. In the former
case we are done. In the latter case, by Lemma 17 we have that $\Gamma$ is
dually-closed Ord-Horn and we ared one by Theorem 10. ∎

## References

  * [BBJK03] Ferdinand Börner, Andrei A. Bulatov, Peter Jeavons, and Andrei A. Krokhin.  Quantified constraints: Algorithms and complexity.  In Computer Science Logic, 17th International Workshop, CSL 2003, 12th Annual Conference of the EACSL, and 8th Kurt Gödel Colloquium, KGC 2003, Vienna, Austria, August 25-30, 2003, Proceedings, pages 58–70, 2003.
  * [BC10] Manuel Bodirsky and Hubie 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.
  * [BK09] Manuel Bodirsky and Jan 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).
  * [BN06] Manuel Bodirsky and Jaroslav Nešetřil.  Constraint satisfaction with countable homogeneous templates.  Journal of Logic and Computation, 16(3):359–373, 2006.
  * [Cam76] Peter J. Cameron.  Transitivity of permutation groups on unordered sets.  Mathematische Zeitschrift, 148:127–139, 1976.
  * [CBW14] Hubie Chen, Manuel Bodirsky, and Michal Wrona.  Tractability of quantified temporal constraints to the max.  Int. J. Algebra Comput., 24(1141), 2014.
  * [Che12] Hubie 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.
  * [CM12] Hubie Chen and Moritz Müller.  An algebraic preservation theorem for aleph-zero categorical quantified constraint satisfaction.  Logical Methods in Computer Science, 9(1), 2012.
  * [CW08a] Witold Charatonik and Michal Wrona.  Quantified positive temporal constraints.  In Proceedings of CSL, pages 94–108, 2008.
  * [CW08b] Witold Charatonik and Michal Wrona.  Tractable quantified constraint satisfaction problems over positive temporal templates.  In LPAR, pages 543–557, 2008.
  * [CW12] Hubie Chen and Michal Wrona.  Guarded ord-horn: A tractable fragment of quantified constraint satisfaction.  In 19th International Symposium on Temporal Representation and Reasoning, TIME 2012, Leicester, United Kingdom, September 12-14, 2012, pages 99–106, 2012.
  * [GJ78] Michael Garey and David Johnson.  A guide to NP-completeness.  CSLI Press, Stanford, 1978.
  * [MSS04] Rolf H. Möhring, Martin Skutella, and Frederik Stork.  Scheduling with and/or precedence constraints.  SIAM Journal on Computing, 33(2):393–415, 2004.
  * [NB95] Bernhard Nebel and Hans-Jürgen Bürckert.  Reasoning about temporal relations: A maximal tractable subclass of Allen’s interval algebra.  Journal of the ACM, 42(1):43–66, 1995.
  * [Sch78] Thomas J. Schaefer.  The complexity of satisfiability problems.  In Proceedings of the Symposium on Theory of Computing (STOC), pages 216–226, 1978.
  * [SW13] Johannes Schmidt and Michal Wrona.  The complexity of abduction for equality constraint languages.  In CSL, pages 615–633, 2013.
  * [Sze86] Ágnes Szendrei.  Clones in universal algebra.  Séminaire de Mathématiques Supérieures. Les Presses de l’Université de Montréal, 1986.
  * [VKvB89] Marc Vilain, Henry Kautz, and Peter van Beek.  Constraint propagation algorithms for temporal reasoning: A revised report.  Reading in Qualitative Reasoning about Physical Systems, pages 373–381, 1989.
  * [Wro12] Michal Wrona.  Syntactically characterizing local-to-global consistency in ord-horn.  In Principles and Practice of Constraint Programming - 18th International Conference, CP 2012, Québec City, QC, Canada, October 8-12, 2012. Proceedings, pages 704–719, 2012.
  * [Wro14a] Michal Wrona.  Local-to-global consistency implies tractability of abduction.  In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, July 27 -31, 2014, Québec City, Québec, Canada., pages 1128–1134, 2014.
  * [Wro14b] Michal Wrona.  Tractability frontier for dually-closed ord-horn quantified constraint satisfaction problems.  In Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part I, pages 535–546, 2014.
  * [ZM21] Dmitriy Zhuk and Barnaby Martin.  The complete classification for quantified equality constraints.  CoRR, abs/2104.00406, 2021.