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.
