October 1, 2018

Florent Madelaine (LACL UPEC)

La conjecture de la dichotomie énoncée en 1993 par Feder et Vardi stipule que tout problème de contraintes est soit dans P, soit NP-complet.
Un phénomène qu’il faut contraster avec le théorème de Ladner qui implique que ceci n’est pas vrai en général (provisio P différent de NP).
Cette conjecture est un théorème depuis 2017 : il y a deux preuves proposées indépendemment par Bulatov et Zhuk.
Entre ces deux dates, cette question a permis de réunir des personnes issues de profils variés (combinatoire, bases de données, logique, algèbre, …).

On n’en voudra pas au lecteur de se poser la question suivante : ce domaine est-il moribond?
Cet exposé sera l’occasion de tenter d’y répondre par la négative après avoir fait un présentation personnelle de ce domaine.