English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Let A be an idempotent algebra on a finite domain. By mediating betweenresults of Chen and Zhuk, we argue that if A satisfies the polynomiallygenerated powers property (PGP) and B is a constraint language invariant underA (that is, in Inv(A)), then QCSP(B) is in NP. In doing this we study thespecial forms of PGP, switchability and collapsibility, in detail, bothalgebraically and logically, addressing various questions such as decidabilityon the way.  We then prove a complexity-theoretic converse in the case of infiniteconstraint languages encoded in propositional logic, that if Inv(A) satisfiesthe exponentially generated powers property (EGP), then QCSP(Inv(A)) isco-NP-hard. Since Zhuk proved that only PGP and EGP are possible, we derive afull dichotomy for the QCSP, justifying what we term the Revised ChenConjecture. This result becomes more significant now the original ChenConjecture is known to be false.  Switchability was introduced by Chen as a generalisation of the already-knowncollapsibility. For three-element domain algebras A that are switchable andomit a G-set, we prove that, for every finite subset D of Inv(A), Pol(D) iscollapsible. The significance of this is that, for QCSP on finite structures(over a three-element domain), all QCSP tractability (in P) explained byswitchability is already explained by collapsibility.

The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation