On the intractability of permuting a block code to minimize trellis complexity
Gavin Bernard Horn, Frank R. Kschischang · IEEE Transactions on Information Theory · 1996
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. 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.