Appears in collection : 19th International Conference on Relational and Algebraic Methods in Computer Science / 19ème Conférence internationale de méthodes relationnelles et algébriques en informatique

The Quantified Constraint Satisfaction Problem (QCSP) is the generalization of the Constraint Satisfaction problem (CSP) where we are allowed to use both existential and universal quantifiers. Formally, the QCSP over a constraint language $\Gamma$ is the problem to evaluate a sentence of the form$$\forall x_{1} \exists y_{1} \forall x_{2} \exists y_{2} \ldots \forall x_{n} \exists y_{n}\left(R_{1}(\ldots) \wedge \ldots \wedge R_{s}(\ldots)\right),$$where $R_{1}, \ldots, R_{s}$ are relations from $\Gamma$. While CSP remains in NP for any $\Gamma, \operatorname{QCSP}(\Gamma)$ can be PSpace-hard, as witnessed by Quantified 3-Satisfiability or Quantified Graph 3Colouring. For many years there was a hope that for any constraint language the QCSP is either in P, NP-complete, or PSpace-complete. Moreover, a very simple conjecture describing the complexity of the QCSP was suggested by Hubie Chen. However, in 2018 together with Mirek Ol_ák and Barnaby Martin we discovered constraint languages for which the QCSP is coNP-complete, DP-complete, and even $\Theta_{2}^{P}$-complete, which refutes the Chen conjecture. Despite the fact that we described the complexity for each constraint language on a 3 -element domain with constants, we did not hope to obtain a complete classification. This year I obtained several results that make me believe that such a classification is closer than it seems. First, I obtained an elementary proof of the PGP reduction, which allows to reduce the QCSP to the CSP. Second, I showed that there is a gap between $\Pi_{2}^{P}$ and PSpace, and found a criterion for the QCSP to be PSpace-hard. In the talk I will discuss the above and some other results.