ИСТИНА

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 is the problem to evaluate a sentence of the form where are relations from . While CSP remains in NP for any , QCSP can be PSpace-hard, as witnessed by Quantified 3-Satisfiability or Quantified Graph 3-Colouring. 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\u{s}\'ak and Barnaby Martin we discovered constraint languages for which the QCSP is coNP-complete, DP-complete, and even -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 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.