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 \dots \forall x_n \exists y_n \; (R_1(\dots)\wedge\dots \wedge R_s(\dots)), \]

where $R_1, \dots, R_s$ are relations from $\Gamma$. While CSP remains in NP for any $\Gamma$, QCSP can be PSpace-hard, as witnessed by Quantified 3-Satisfiability or Quantified Graph 3-Colouring. Moreover, in 2018 we discovered constraint languages for which the QCSP is coNP-complete, DP-complete, and even $\Theta_2^P$-complete. Thus, already six complexity classes can be expressed via QCSP, which is why we did not hope to obtain a complete classification of the complexity.

Last 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. Finally, I found the missing complexity class, and now I believe that for any constraint language the QCSP is either in P, or NP-complete, or coNP-complete, or DP-complete, or $\Theta_2^P$-complete, or $\Pi_2^P$-complete, or PSpace-complete.