The problem of compact tables is to maximise the overlap when building a word that is to include permutations of every given words (all the words being the same length). This problem is shown to be NP-complete in the general case, and some specific restrictions are studied.
To show this on a small example (beyond what is in the article), imagine that in a game (like checkers) if blue takes red, on a result of 1, both are eliminated, on 2 or 3, red remains and blue remains in the other cases. If red takes blue, results 1 to 4 make red win and on 5 to 6, blue wins. The compact table in this case would be to keep the table as is in the blue versus red, add +2 if red versus blue, with results 7 and 8 letting red win.
About this article
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.
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.
The documents
Citing this publication
This publication was made in the proceedings of the JAC 2008 conference that took place this year in Uzès (France). This article was furthermore put under the CC-BY-ND et inserted automatically in HAL (and from there, in 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}
}