Dmitriy Zhuk

Heptachotomy of QCSPs


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.

Recording on zoom.us