National Institute of the Republic of Serbia
ὅδε οἶκος, ὦ ἑταῖρε, μνημεῖον ἐστιν ζωῶν τῶν σοφῶν ἀνδρῶν, καὶ τῶν ἔργων αὐτῶν
PROGRAM
| ODELJENJE ZA MATEMATIKU MATEMATIČKOG INSTITUTA SANU |
PROGRAM ZA FEBRUAR 2025.
Četvrtak, 27.02.2025. u 14:15, Kneza Mihaila 36, sala 301f i Online
Petar Marković, DMI Novi Sad
THE DICHOTOMY THEOREM ON THE COMPUTATIONAL COMPLEXITY OF THE CONSTRAINT SATISFACTION PROBLEM
In the first part of the lecture I will cover the history, motivation and the formulation of the Constraint Satisfaction Problem, and its computational complexity, which was a central topic of research for a couple of decades. The Dichotomy Conjecture, now the Dichotomy Theorem, states that the Constraint Satisfaction Problem is always either tractable or NP-complete. Which of these two cases occurs depends entirely on the finite model, the so-called "template", which is a fixed parameter of the Constraint Satisfaction Problem). Next I will give an overview of the methods and techniques from various areas which were used in the proofs of the partial results leading up to the Dichotomy Theorem, including its two full proofs. The last part of the lecture will cover some of the results which simplify and/or unite the two proofs of the Dichotomy Theorem. Time permitting, I will mention the generalizations of the Constraint Satisfaction Problem which are the focus of most recent research in the area, and which motivate us to work on simplifying the proofs of an already proved result.