On the Computational Complexity of Hidden Markov Model Identification
Abstract
Identification is the task of recovering the parameters of an unknown ground-truth model from sampled data. When parameters other than the ground truth induce the same output distribution, data alone does not provide enough information to recover the ground truth, and the model is thus called unidentifiable. We study the identifiability problem for hidden Markov models (HMMs): given an HMM, is it identifiable? Existing work on HMM identification establishes conditions under which the ground-truth HMM can be identified. However, most of these conditions are sufficient but not necessary, meaning that, when a model does not satisfy them, its identifiability remains inconclusive. We instead take a computational perspective: is there a sound and complete algorithm that decides whether a given HMM is identifiable, and if so, what is the complexity of this decision problem? We consider the decision problems arising from the various notions of identifiability in the literature, including deterministic, generic, global, local, state-permutation- invariant, and finite-alphabet identifiability. We show that all of these problems are decidable in PSPACE, via reductions to the theory of the reals at various levels of its quantifier-alternation hierarchy. We further show that the deterministic variants are already coETR-hard (and hence coNP-hard) for simply parameterized families.
Related
- Gated Spatial Hidden Markov Models for Classification in Histological Samples, With Application to Muscle Fiber‐Typing
- Accumulated-Variance Functionals of Hidden Markov and Semi-Markov Processes: Finite-Sample Upper and Lower Bounds
- Generalized Infinite Hidden Markov Models
- Equilibrium prices under hidden Markov fundamentals
- A latent space hidden Markov model for clustering views in longitudinal multilayer networks
BibTeX
@misc{zubia2026computational,
title = {{On the Computational Complexity of Hidden Markov Model Identification}},
author = {Markel Zubia and Nils Jansen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.09104},
eprint = {2610.09104},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.09104},
}
RIS
TY - UNPB
TI - On the Computational Complexity of Hidden Markov Model Identification
AU - Markel Zubia
AU - Nils Jansen
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.09104
UR - https://arxiv.org/abs/2610.09104
AB - Identification is the task of recovering the parameters of an unknown ground-truth model from sampled data. When parameters other than the ground truth induce the same output distribution, data alone does not provide enough information to recover the ground truth, and the model is thus called unidentifiable. We study the identifiability problem for hidden Markov models (HMMs): given an HMM, is it identifiable? Existing work on HMM identification establishes conditions under which the ground-truth HMM can be identified. However, most of these conditions are sufficient but not necessary, meaning that, when a model does not satisfy them, its identifiability remains inconclusive. We instead take a computational perspective: is there a sound and complete algorithm that decides whether a given HMM is identifiable, and if so, what is the complexity of this decision problem? We consider the decision problems arising from the various notions of identifiability in the literature, including deterministic, generic, global, local, state-permutation- invariant, and finite-alphabet identifiability. We show that all of these problems are decidable in PSPACE, via reductions to the theory of the reals at various levels of its quantifier-alternation hierarchy. We further show that the deterministic variants are already coETR-hard (and hence coNP-hard) for simply parameterized families.
ER -