Johann Brault-Baron (lif, Marseille)

Le problème CSP (Constraint Satisfaction Problem) consiste à déterminer, étant donné un ensemble de contraintes, s’il existe une solution, c’est-à-dire un ensemble d’affectations des variables qui satisfait toutes les contraintes. C’est un problème NP-complet.

Nous nous intéressons ici au problème #CSP qui consiste à déterminer, étant donné un ensemble de contraintes, le nombre de telles solutions. C’est donc un problème NP-difficile.

À l’instar du problème CSP, on peut restreindre le type de contraintes possibles afin de s’assurer que le problème est polynomial. Cette approche a montré rapidement ses limites, et on s’est donc penché sur une autre alternative, qui consiste à placer des restrictions sur le graphe (ou l’hypergraphe) de contraintes, appelée « restrictions structurales ».

Cette approche a amené à définir de nombreuses nouvelles classes polynomiales, qui ont été toutes décrites et « synthétisées » dans une contribution récente et marquante de Sæther, Telle et Vatshelle. Les auteurs définissent un paramètre, qui, d’un certain point de vue, indique l’efficacité de tout algorithme de type « diviser pour régner ». Lorsque ce paramètre est borné, la classe correspondante a un problème #CSP de complexité polynomiale. Jusqu’à présent, toutes les restrictions structurales envisagées sont des cas particuliers d’une telle situation.

On décrit dans cet exposé une classe polynomiale pour #CSP qui échappe (étonnamment) à ce cadre, et qui a de plus l’avantage d’être reconnaissable en temps polynomial.