SZTE Bolyai Intézet - Petar Markovic: The Constraint Satisfaction Problem Dichotomy Conjecture: History, Proofs and Generalizations

$help$

$Év szerint$	$Hónap szerint$	$Ugrás a hónaphoz$
Év szerint	Hónap szerint	Ugrás a hónaphoz

Petar Markovic: The Constraint Satisfaction Problem Dichotomy Conjecture: History, Proofs and Generalizations

$iCal fájl letöltése$

$Esemény exportálása$ Esemény exportálása

A leírásban a formázás megtartása (csak néhny naptár alkalmazás támogatja)

Szerda, 28. Február 2024, 10:10 - 11:40

The Constraint Satisfaction Problem was defined in the 1990s, inspired by certain topics in Descriptive Complexity. At that time, the Dichotomy Conjecture on the complexity of the Constraint Satisfaction Problem was posed. The Dichotomy Conjecture was proved a quarter of a century later, in 2017, independently by Andrei Bulatov and Dmitriy Zhuk. In this lecture I will define the Constraint Satisfaction Problem, motivate the Dichotomy Conjecture, and survey the main ideas in the proofs by Bulatov and Zhuk. In the final part, I will briefly describe the two most popular generalizations which are a focus of research by numerous teams since the proof of the Dichotomy Conjecture, introduce a third possibility of generalizing the Dichotomy Conjecture and argue why this third topic should also be in the focus of research.

Vissza