00:00:00 / 00:00:00
2 5

Quantified constraint satisfaction problem: towards the classification of complexity

By Dmitriy Zhuk

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.

Information about the video

Citation data

  • DOI 10.24350/CIRM.V.19828803
  • Cite this video Zhuk, Dmitriy (02/11/2021). Quantified constraint satisfaction problem: towards the classification of complexity. CIRM. Audiovisual resource. DOI: 10.24350/CIRM.V.19828803
  • URL https://dx.doi.org/10.24350/CIRM.V.19828803

Bibliography

  • ZHUK, Dmitriy et MARTIN, Barnaby. QCSP monsters and the demise of the Chen Conjecture. In : Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. 2020. p. 91-104. - https://doi.org/10.1145/3357713.3384232
  • ZHUK, Dmitriy. The complexity of the Quantified CSP having the polynomially generated powers property. arXiv preprint arXiv:2110.09504, 2021. - https://arxiv.org/abs/2110.09504
  • ZHUK, Dmitriy et MARTIN, Barnaby. The complete classification for quantified equality constraints. arXiv preprint arXiv:2104.00406, 2021. - https://arxiv.org/abs/2104.00406

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow




Register

  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
    community
  • Get notification updates
    for your favorite subjects
Give feedback