Наредни састанак Семинара биће одржан у четвртак, 27. фебруара 2025. године, у сали 301ф Математичког института САНУ са почетком у 14.15.
Предавач: Петар Марковић, ДМИ Нови Сад
Наслов предавања: 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.
Напомена: Предавање је могуће пратити на даљину путем Zoom платформе
https://zoom.us/j/91360894651?pwd=gMbP5rMDEvUmkHzHMRLLtKniwSGTQc.1
Meeting ID: 913 6089 4651
Passcode: 698920