The complexity of the max word problem and the power of one-way interactive proof systems (Q1312183)

We study the complexity of the max word problem for matrices, a variation of the well-known word problem for matrices. We show that the problem is NP-complete, and cannot be approximated within any constant factor, unless \(P=NP\). We describe applications of this result to probabilistic finite state automata, rational series and \(K\)-regular sequences. Our proof is novel in that it employs the theory of interactive proof systems, rather than a standard reduction argument. As another consequence of our results, we characterize NP exactly in terms of one- way interactive proof systems.