DIMACS TR: 98-02

On the Complexity of Generation in Ternary Hamming Spaces

Authors: Endre Boros, Peter L. Hammer, Frederica Ricca and Bruno Simeone


In this paper, a follow-up of DIMACS Report 98-01, we continue to study ternary Hamming spaces $\TT^n$, where $\TT=\{0,1,2\}$, and their generators. In particular, we are interested in the computational complexity of the generation of all vectors with respect to a specific generator $G\subseteq \TT^n$. We consider several parameters, i.e., depth and load, which provide alternative ways to measure the computational effort required in order to generate all points of $\TT^n$ starting from those of $G$. We establish lower and upper bounds on the minimum depth and the minimum load for a generator in, and prove that some of them are sharp.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-02.ps.gz
DIMACS Home Page