  Hidden Markov models (HMMs) and their variants were successfully used for
several sequence annotation tasks. Traditionally, inference with HMMs is done
using the Viterbi and posterior decoding algorithms. However, recently a
variety of different optimization criteria and associated computational
problems were proposed. In this paper, we consider three HMM decoding criteria
and prove their NP hardness. These criteria consider the set of states used to
generate a certain sequence, but abstract from the exact locations of regions
emitted by individual states. We also illustrate experimentally that these
criteria are useful for HIV recombination detection.
