Problèmes de satisfaction de contraintes avec listes résolubles en espace logarithmique

 

Benoit Larose

Collège Champlain

 

Domaine : structures abstraites

Programme de recherche pour les enseignants de collège

Concours 2013-2014

Sans conteste, le thème central de l'algorithmique est de déterminer ce qui fait qu'un problème de décision donné peut ou ne peut pas être résolu par un algorithme efficace : à titre d'exemple, le fameux problème P vs NP consiste à déterminer si un algorithme efficace existe pour un quelconque problème dit NP-complet. Bien que ce problème soit hors de portée pour l'instant, un grand nombre de questions analogues peuvent être abordées et font l'objet de recherches intensives.

Les problèmes de satisfaction de contraintes (CSP) offrent un cadre à la fois suffisamment vaste et bien délimité pour étudier ces questions : un CSP consiste à déterminer, étant donné un certain nombre de variables et des contraintes sur celles-ci, si l'on peut assigner des valeurs aux variables qui satisfont à toutes les contraintes: ces problèmes sont étudiés dans divers domaines comme l'intelligence artificielle, les bases de données, l'optimisation, etc. Le problème général est NP-complet, mais en restreignant la nature des contraintes on peut obtenir des cas particuliers admettant des algorithmes efficaces.

Une série de conjectures centrales au domaine prédisent la forme que devraient prendre les contraintes pour que le CSP admette un algorithme qui utilise peu de ressources (temps, espace); l'objectif principal de notre projet de recherche est de tenter de démontrer ces conjectures dans certains cas spécifiques de CSP avec listes.