Семинар МЛ ТИ: "On the complexity of the Quantified Constraint Satisfaction Problem"
В среду, 11 октября, приглашаем Вас на семинар лаборатории теоретической информатики.
Семинар пройдет онлайн с 18:10 до 19:30.
Название: On the complexity of the Quantified Constraint Satisfaction Problem
Докладчик: Dmitry Zhuk
Аннотация: The Quantified Constraint Satisfaction Problem (QCSP) is the generalization of the Constraint Satisfaction problem (CSP) where both existential and universal quantifiers are allowed. Formally, the QCSP over a constraint language is the problem to evaluate a sentence with both quantifiers, predicates from the constraint language, and conjunctions.
The goal is to describe complexity of this problem for all constraint languages. In 2018 we discovered constraint languages for which the QCSP is coNP-complete, DP-complete, and even $\Theta_{2}^{P}$-complete, which made a complete classification hardly possible. Recently, 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.