[ONLINE] Семинар МЛ ТИ: "On the Complexity of the Surjective Constraint Satisfaction Problem"

3 июня в 18:10 на семинаре лаборатории теоретической информатики состоится  онлайн доклад  Дмитрия Жука  "On the Complexity of the Surjective Constraint Satisfaction Problem"

Abstract: 

Constraint Satisfaction Problem (CSP) is the problem of deciding whether there exists an assignment to a set of variables subject to some specified constraints. Surjective Constraint Satisfaction Problem (SCSP) is the variant of CSP where we require the solution to be surjective that is all values from the domain appear in the solution. Unlike the CSP, where the complexity was classified for all constraint languages, the complexity of the SCSP remains unknown even for very simple constraint languages.

In the talk we will discuss recent results of the author on the complexity of the SCSP. First, I proved NP-Hardness for one of the most popular constraint languages with unknown complexity (so called No-Rainbow Problem). Additionally, I found a counter-example to a widely-believed conjecture describing the complexity of the SCSP for all constraint languages.

Доклад пройдет в Zoom, необходима регистрация.

#HSEresearch