Publication:4035692
From MaRDI portal
zbMath0773.68039MaRDI QIDQ4035692
Publication date: 18 May 1993
NP-complete; interactive proof systems; rational series; probabilistic finite state automata; \(k\)-regular sequences; word problem for matrices
68Q25: Analysis of algorithms and problem complexity
Related Items
The complexity of the max word problem and the power of one-way interactive proof systems, On the complexity of partially observed Markov decision processes, The complexity of approximating a nonlinear program