Computational Complexity of the Minimum State Probabilistic Finite State Learning Problem on Finite Data Sets.
Elisabeth Paulson, Christopher H. Griffin · arXiv (Cornell University) · 2015
In this paper, we study the problem of determining a minimum state probabilistic finite state machine capable of generating statistically identical symbol sequences to samples provided. This problem is qualitatively similar to the classical Hidden Markov Model problem and has been studied from a practical point of view in several works beginning with the work presented in: Shalizi, C.R., Shalizi, K.L., Crutchfield, J.P. (2002) [arXiv:cs/0210025]. In this paper, we show that the underlying problem is $\mathrm{NP}$-hard and thus all existing polynomial time algorithms must be approximations on finite data sets. Using our $\mathrm{NP}$-hardness proof, we show how to construct a provably correct algorithm for constructing a minimum state probabilistic finite state machine given data and empirically study its running time.