Notice: Undefined index: in /opt/lipn/software/dotclear2-svn/trunk/plugins/stacker/class.stacker.php on line 188

This publication in the proceedings of the JAC 2008 conference was a bit out of scope, and therefore classified as an exploratory paper. I made my own comments on the conference including a few pictures on a separate page.

The inspiration for this article comes from my wargaming experience. It is a bit spoken-of in the slides, but the main point is that when considering the tables typically found in wargames, you often use modifiers (e.g. +1 to the result of the dice roll). While the tables are usually in ascending order of effect (or descending), when modifiers come into play, the result 11 (which is 10 as the result of the 10-sided dice + 1) can be of a lower effect than a 10 + 0 result. This is considered normal; what you have to consider is that when you do that, you can roll in the range 2-11 only and you should compare the 11 result to the 1 result (which is no more possible) instead.

The main result

As explained in the slides and in the introduction, this problem is a variant of the superword problem: given a set of words (of the same length), one wants the shortest word containing contiguously all the words of the collection, or any permutation of these words (without this addition, there are already well known results, see e.g. De Bruijn graphs). For example, if I give the words aabc, abbb and abcc, the word bbabcc is a correct answer to the problem.

The problem is NP-complete (and thus difficult). It is also #P-complete, which means that if one can count the answers to this problem, one can count the answers to many others. The reduction is done from the hamiltonian path problem (definition).

The restrictions remain NP-complete as soon as three letter words or more are concerned. If one has two letters words only (head or tail somehow), there exists a polynomial answer (based on the eulerian path problem).

An interesting open problem appeared during the writing of this paper. There are $\ell+k-1\choose\ell$ possible words of k letters and length $\ell$. One could imagine placing these words with a maximum overlap adding only one letter per word. Strangely enough, this is not possible. The length of the smallest word containing a permutation of all the words of k letters of length $\ell$ remains a mystery.

Citing this publication

This publication was made in the proceedings of the conference JAC 2008 which took place in Uzès (France). Remark that this article was put under a CC-BY-ND license and automatically inserted in HAL (and should be automatically in arXiv, too).

@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}}