1 octobre 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.