## Séminaire Algorithmique |

Le séminaire a lieu **le mardi à 11 h 45** (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

# Résumé du séminaire du Mardi 23 Mai 2017

*The Complexity of Quantified Constraints*

## par Barnaby Martin ( Middlesex University London)

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
co-NP-hard, and the borderline is given precisely according to
whether A enjoys the polynomially-generated powers (PGP) property.
This reduces the complexity classification problem for QCSPs to
that of CSPs, modulo that co-NP-hard cases might have complexity
rising up to Pspace-complete. 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 exponentially-generated powers (EGP), proved by
Dmitriy Zhuk in 2015, married carefully to previous work of
Chen.