Autour de JAC 2008
Cette publication dans JAC 2008 (Journées Automates Cellulaires, le titre a été forcé en français pour faire penser à Jacques Mazoyer) était un peu limite, car assez hors-sujet : pas de mention d’automate cellulaire, juste un automate probabiliste. Ceci dit, le problème a intéressé plusieurs personnes lors de l’exposé, et une application à la programmation d’automates a même été suggérée. J’ai fait mon propre commentaire de la conférence agrémentée de photographies.
Autour de cet article
Le sujet de cet article est tiré de constatations que j’ai faite pendant des parties de wargame (définition). Les tables utilisées dans ces jeux donnent souvent des résultats croissants en fonction d’un jet de dé ; plus on fait, mieux c’est. À cause de la diversité des situations, il y a souvent des modificateurs (si on plus de tanks, on rajoute 2 ; si on a de l’aviation, on rajoute aussi 2 au jet de dé ; si on a les deux, on rajoute 4). Et des fois apparaissent dans les tables des résultats plus faibles dans le haut que dans le bas. Ce qui s’explique par le fait que ce qui compte du point de vue du jet de dé, ce n’est pas le résultat précis obtenu, mais la probabilité de l’obtenir. Donc notamment la différence entre la ligne ajoutée par le modificateur (ou les lignes) et les lignes qu’on ne peut plus atteindre (par exemple, si le résultat 1 signifie un échec total de l’attaque, un bonus de +1 permet de ne pas avoir d’échec total, et c’est déjà un avantage, même si le résultat maximal+1 n’est qu’un échec partiel). Nous nous sommes aperçus avec Jean-Yves qu’en construisant une telle table, le problème était assez complexe. De fait, il est NP-complet. Je remercie d’ailleurs encore une fois Pierre Borgnat pour nous avoir expliqué ce particularisme de la table d’assaut d’Europa Universalis (définition).
Le résultat essentiel
Comme expliqué en introduction et dans les transparents de l’exposé, il s’agit en fait d’une variante du problème du supermot : étant donné une collection de mots (ici, tous de la même longueur), il s’agit de trouver le plus petit mot qui contient au moins une fois de façon contiguë chacun des mots de la collection. Par exemple, si je prends les mots aabc, abbb et abcc, le mot bbabcc est une réponse correcte au problème puisque les trois mots apparaissent.
Le problème est NP-complet (donc difficile à résoudre). Il est aussi #P-complet, ce qui signifie que si on sait compter le nombre de solutions de ce problème, on sait aussi compter le nombre de solutions de beaucoup d’autres problèmes. La réduction est faite depuis le problème du chemin hamiltonien (définition).
Les restrictions restent NP-complètes dès que l’on garde des mots d’au moins trois lettres. Lorsque l’on a seulement deux lettres (pile ou face, en quelque sorte), il existe une méthode polynomiale pour résoudre le problème (basée sur le chemin eulérien).
Un problème ouvert intéressant est apparu lors de la rédaction de cet article. Il y a 
mots possibles de k lettres de longueur 
. On pourrait donc imaginer placer ses mots les uns à la suite des autres en passant de l’un à l’autre par une seule lettre. Étonnament, ce n’est pas possible. La longueur du plus petit mot contenant une permutation de tous les mots de k lettres de longueur reste donc un mystère.
Citer cette publication
Cette publication a été faite dans les actes de la conférence JAC 2008 qui s’est déroulée cette année-là à Uzès (France). On notera que cet article a été mis sous licence CC-BY-ND et insérée automatiquement dans HAL (et normalement aussi dans arXiv).
@InProceedings{dm08,
author = {Jean-Christophe Dubacq and Jean-Yves Moyen},
title = {Study of the NP-completeness of the Compact Table
problem},
booktitle = {Proceedings of the First Symposium on Cellular Automata Journ\'{e}es Automates Cellulaires},
pages = {451--464},
year = {2008},
editor = {Bruno Durand},
address = {Moscow},
month = apr,
publisher = {MCCME Publishing House},
isbn = {978-5-94057-377-7}
}