On the Complexity of Generation in Ternary Hamming Spaces

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

ABSTRACT

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