On the Chen Conjecture regarding the complexity of QCSPs

2016/07/13 by Barnaby Martin, Martin, Barnaby
Computer Science · Engineering · #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #cs.LO #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1607.03819

arxiv created 2016/07/13 · openalex publication_date 2016/07/13 · arxiv updated 2016/07/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let A be an idempotent algebra on a finite domain. We combine results of Chen 2008 and Zhuk 2015 to argue that if Inv(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.

Related

• The complexity of quantified constraints using the algebraic formulation
• The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation
• QCSP monsters and the demise of the Chen Conjecture
• From complexity to algebra and back: digraph classes, collapsibility and the PGP
• The complexity of the Quantified CSP having the polynomially generated powers property