|
SEMINARS |
|
On the complexity of the Quantified Constraint Satisfaction Problem D. N. Zhuk |
|||
Abstract: 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 Language: English Website: https://cs.hse.ru/big-data/tcs-lab/announcements/864175338.html |