Régis Barbanchon (GREYC)

De nombreux problèmes NP-complets ne sont pas seulement vérifiables en temps polynômial mais aussi en temps linéaire. Parmi ceux-ci, certains sont linéairement réductibles entre eux, alors que l’on conjecture que c’est impossible pour d’autres. Hamilton et Sat sont interessants sous cet aspect.

  • Le problème Hamilton est celui de l’existence d’un chemin visitant une fois et une seule tous les sommets d’un graphe donné. Il existe des variantes à ce problème selon la nature du chemin demandé (extrémités libres ou fixées, cycle) ainsi que selon la nature du graphe (orienté, non orienté, non orienté à degré borné).
  • Le problème Sat est celui de l’existence d’une valuation satisfaisant un ensemble de clauses de la logique propositionnelle. Lorsque le graphe biparti représentant l’appartenance des variables aux clauses est planaire, le problème est alors Sat planaire.

Une réduction exacte est une réduction à la fois linéaire et parcimonieuse (ie. elle preserve le nombre de solutions). Il est connu que les variantes de Hamilton non-planaires sont équivalentes sous interréduction exacte lorsque le degré des graphes n’est pas borné. Il est également connu que Sat non-planaire est exactement réductible à Hamilton non-planaire. A notre connaissance, il n’existe pas les mêmes résultats pour les graphes planaires et/ou à degré borné.

Dans cet exposé, nous établirons principalement trois choses: * Toutes les variantes citées de Hamilton non-planaires sont exactement interréductibles, même lorsque le degré est borné à 3; * Toutes les variantes citées de Hamilton planaires sont exactement interréductibles, même lorsque le degré est borné à 3; * Sat planaire est exactement réductible à Hamilton planaire. Ces résultats seront obtenus par une méthode uniforme de réduction utilisant un arsenal homogène de gadgets modulaires inspirés des circuits électroniques. Nous pensons que s’il est très difficile de montrer que Hamilton n’est pas linéairement réductible à Sat, il sera peut-être plus facile de d’obtenir un résultat de non expressibilité si la réduction impliquée est plus stricte. A cet effet, la transformation exacte représente une piste.