Sur une classe polynomiale relationnelle pour les CSP binaires

Abstract

Trouver une solution à un probl ème de satisfaction de contraintes est en g én éral un probl ème NP-diffi cile. Ainsi, identifier une nouvelle classe polynomiale de CSP, en d'autres termes, une classe de probl èmes de satisfaction de contraintes pour lesquelles il existe une m éthode de réconnaissance et de r ésolution de complexit é polynomiale, constitue un axe de recherche fondamental dans l' étude des CSPs. Dans cet article, nous pr ésentons une nouvelle classe polynomiale relationnelle pour les CSPs binaires. Tout d'abord nous pr ésentons un nouvel op érateur ternaire que nous avons appel é mjx. Nous d écrivons ensuite les relations ferm ées par cet op érateur en proposant un algorithme d'identification de ces relations. Afin de r éduire la complexit é spatiale et temporelle des traitements, nous d éfinissons une nouvelle m éthode de stockage de ces relations qui permet de r éduire la complexit é de chemin consistance, ce dernier niveau de consistance étant suffi sant pour r ésoudre les instances de la classe propos ée.