Complexité de Forward Checking et Hiérarchie des Décompositions de CSP Revisitées

National audienceDans cette contribution, nous proposons une nouvelle évaluation de la complexité de la procédure Forward Checking appliquée à la résolution de CSP n-aires à domaines finis. Généralement, cette évaluation prend en compte la taille des domaines associés aux variables. Ici, nous l'exprimons relativement à la taille des relations de compatibilité associées aux contraintes. Cette nouvelle approche permet ainsi, parfois, de fournir une meilleure borne de complexité théorique. Nous montrons l'intérêt essentiel de cette démarche en revenant sur les résultats proposés dans [10] et qui concernent la hiérarchie des décompositions de CSP (comparaisons des méthodes de décompositions structurelles), et qui constituent un résultat fondamental du domaine. Nous invalidons une partie de ces résultats en démontrant notamment que le concept de décomposition en hyperarbres, situé au sommet de cette hiérarchie, n'est finalement pas meilleur que celui de décomposition arborescente. Ce résultat, essentiellement théorique, s'avère toutefois en adéquation avec les observations expérimentales obtenues ces dernières années au sein de la communauté