Naredni sastanak Seminara biće održan u četvrtak, 27. februara 2025. godine, u sali 301f Matematičkog instituta SANU sa početkom u 14.15.

Predavač: Petar Marković, DMI Novi Sad

Naslov predavanja: THE DICHOTOMY THEOREM ON THE COMPUTATIONAL COMPLEXITY OF THE CONSTRAINT SATISFACTION PROBLEM

Apstrakt: 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.

Napomena:
Predavanje je moguće pratiti na daljinu putem Zoom platforme
https://zoom.us/j/91360894651?pwd=gMbP5rMDEvUmkHzHMRLLtKniwSGTQc.1

Meeting ID: 913 6089 4651
Passcode: 698920