Let 𝔸 be an idempotent algebra on a finite domain. By mediating between results of Chen [ 1 ] and Zhuk [ 2 ], we argue that if 𝔸 satisfies the polynomially generated powers property (PGP) and ℬ is a constraint language invariant under 𝔸 (i.e., in Inv(𝔸)), then QCSP ℬ is in NP. In doing this, we study the special forms of PGP, switchability, and collapsibility, in detail, both algebraically and logically, addressing various questions such as decidability on the way. We then prove a complexity-theoretic converse in the case of infinite constraint languages encoded in propositional logic, that if Inv}(𝔸) satisfies the exponentially generated powers property (EGP), then QCSP (Inv(𝔸)) is co-NP-hard. Since Zhuk proved that only PGP and EGP are possible, we derive a full dichotomy for the QCSP, justifying what we term the Revised Chen Conjecture . This result becomes more significant now that the original Chen Conjecture (see [ 3 ]) is known to be false [ 4 ]. Switchability was introduced by Chen [ 1 ] as a generalization of the already-known collapsibility [ 5 ]. There, an algebra 𝔸 :=({ 0,1,2}; r ) was given that is switchable and not collapsible. We prove that, for all finite subsets Δ of Inv (𝔸 A), Pol (Δ) is collapsible. The significance of this is that, for QCSP on finite structures, it is still possible all QCSP tractability (in NP) explained by switchability is already explained by collapsibility. At least, no counterexample is known to this.

Let A be an idempotent algebra on a finite domain. We combine results of Chen, Zhuk and Carvalho et al. to argue that if A satisfies the polynomially generated powers property (PGP), then QCSP(Inv(A)) is in NP. We then use the result of Zhuk to prove a converse, that if Inv(A) satisfies the exponentially generated powers property (EGP), then QCSP(Inv(A)) is co-NP-hard. Since Zhuk proved that only PGP and EGP are possible, we derive a full dichotomy for the QCSP, justifying the moral correctness of what we term the Chen Conjecture. We examine in closer detail the situation for domains of size three. Over any finite domain, the only type of PGP that can occur is switchability. Switchability was introduced by Chen as a generalisation of the already-known Collapsibility. For three-element domain algebras A that are Switchable, we prove that for every finite subset Delta of Inv(A), Pol(Delta) is Collapsible. The significance of this is that, for QCSP on finite structures (over three-element domain), all QCSP tractability explained by Switchability is already explained by Collapsibility. Finally, we present a three-element domain complexity classification vignette, using known as well as derived results.

Inspired by computational complexity results for the quantified constraint satisfaction problem, we study the clones of idem potent polymorphisms of certain digraph classes. Our first results are two algebraic dichotomy, even "gap", theorems. Building on and extending [Martin CP'11], we prove that partially reflexive paths bequeath a set of idem potent polymorphisms whose associated clone algebra has: either the polynomially generated powers property (PGP), or the exponentially generated powers property (EGP). Similarly, we build on [DaMM ICALP'14] to prove that semi complete digraphs have the same property. These gap theorems are further motivated by new evidence that PGP could be the algebraic explanation that a QCSP is in NP even for unbounded alternation. Along the way we also effect a study of a concrete form of PGP known as collapsibility, tying together the algebraic and structural threads from [Chen Sicomp'08], and show that collapsibility is equivalent to its Pi2-restriction. We also give a decision procedure for k-collapsibility from a singleton source of a finite structure (a form of collapsibility which covers all known examples of PGP for finite structures). Finally, we present a new QCSP trichotomy result, for partially reflexive paths with constants. Without constants it is known these QCSPs are either in NL or Pspace-complete [Martin CP'11], but we prove that with constants they attain the three complexities NL, NP-complete and Pspace-complete.

The study of constraint satisfaction problems definable in various fragments of Datalog has recently gained considerable importance. We consider constraint satisfaction problems that are definable in the smallest natural recursive fragment of Datalog- monadic linear Datalog with at most one EDB per rule, and also in the smallest non-linear extension of this fragment. We give combinatorial and algebraic characterisations of such problems, in terms of homomorphism dualities and lattice operations, respectively. We then apply our results to study graph H-colouring problems. 1

The study of constraint satisfaction problems definable in various fragments of Datalog has recently gained considerable importance. We consider constraint satisfaction problems that are definable in the smallest natural recursive fragment of Datalog - monadic linear Datalog with at most one EDB per rule. We give combinatorial and algebraic characterisations of such problems, in terms of caterpillar dualities and lattice operations, respectively. We then apply our results to study graph H-colouring problems.