The complexity of the max word problem and the power of one-way interactive proof systems
type: Item
instance of: scholarly article
title: The complexity of the max word problem and the power of one-way interactive proof systems
zbMATH Open document ID: 0788.68050
DOI: 10.1007/BF01271372
author: Anne Condon
published in: Computational Complexity
publication date: 1994-01-19T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 488274
zbMATH Keywords: max word problem for matrices
zbMATH Keywords: word problem for matrices
zbMATH Keywords: NP-complete
zbMATH Keywords: probabilistic finite state automata
zbMATH Keywords: interactive proof systems
MaRDI profile type: Publication
cites work: Q3975928
cites work: Q4230322
cites work: Non-deterministic exponential time has two-prover interactive protocols
cites work: Q4035692
cites work: Space-bounded probabilistic game automata
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: The knowledge complexity of interactive proof-systems
cites work: Word Problems Solvable in Logspace
cites work: Algebraic methods for interactive proof systems
cites work: Q5643915
cites work: Probabilistic automata
cites work: Q5677651
cites work: Q4155837
description: scientific article; zbMATH DE number 488274