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

We give a surprising classification for the computational complexity of theQuantified Constraint Satisfaction Problem over a constraint language $\Gamma$,QCSP$(\Gamma)$, where $\Gamma$ is a finite language over $3$ elements whichcontains all constants. In particular, such problems are either in P,NP-complete, co-NP-complete or PSpace-complete. Our classification refutes thehitherto widely-believed Chen Conjecture.  Additionally, we show that already on a 4-element domain there exists aconstraint language $\Gamma$ such that QCSP$(\Gamma)$ is DP-complete (fromBoolean Hierarchy), and on a 10-element domain there exists a constraintlanguage giving the complexity class $\Theta_{2}^{P}$.  Meanwhile, we prove the Chen Conjecture for finite conservative languages$\Gamma$. If the polymorphism clone of $\Gamma$ has the polynomially generatedpowers (PGP) property then QCSP$(\Gamma)$ is in NP. Otherwise, the polymorphismclone of $\Gamma$ has the exponentially generated powers (EGP) property andQCSP$(\Gamma)$ is PSpace-complete.

QCSP monsters and the demise of the Chen Conjecture