The Complexity of Quantified Constraints

14:00 17th November 2016 ( week 6, Michaelmas Term 2016 )Room 051, Wolfson Building, Parks Road
We elaborate the complexity of the Quantified Constraint Satisfaction Problem, QCSP(A), where A is a finite idempotent algebra. Such a problem is either in NP or is coNPhard, and the borderline is given precisely according to whether A enjoys the polynomiallygenerated powers (PGP) property. This reduces the complexity classification problem for QCSPs to that of CSPs, modulo that coNPhard cases might have complexity rising up to Pspacecomplete. Our result requires infinite languages, but in this realm represents the proof of a slightly weaker form of a conjecture for QCSP complexity made by Hubie Chen in 2012. The result relies heavily on the algebraic dichotomy between PGP and exponentiallygenerated powers (EGP), proved by Dmitriy Zhuk in 2015, married carefully to previous work of Chen.