On the intractability of permuting a block code to minimize trellis complexity

An important problem in the theory and application of block-code trellises is to find a coordinate permutation of a given code to minimize the trellis complexity. In this correspondence we show that the problem of finding a coordinate permutation that minimizes the number of vertices at a given depth in the minimal trellis for a binary linear block code is NP-complete. Index Terms - Permutation trellis complexity, NP-completeness.