The "art of trellis decoding" is computationally hard-for large fields
Kavita. A Jain, Ion Măndoiu, V.V. Vazirani · 2002
The problem of minimizing the trellis complexity of a code by coordinate permutation is proven NP-hard for three different measures of trellis complexity, provided the field over which the code is specified is not fixed.