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

DOI10.1007/BF01271372zbMath0788.68050MaRDI QIDQ1312183

Anne Condon

Publication date: 19 January 1994

Published in: Computational Complexity (Search for Journal in Brave)

zbMATH Keywords

NP-completeinteractive proof systemsprobabilistic finite state automatamax word problem for matricesword problem for matrices

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

The hardness of approximate optima in lattices, codes, and systems of linear equations, The complexity of debate checking, Constant-space, constant-randomness verifiers with arbitrarily small error

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Non-deterministic exponential time has two-prover interactive protocols
• Word Problems Solvable in Logspace
• Computational Complexity of Probabilistic Turing Machines
• Algebraic methods for interactive proof systems
• Space-bounded probabilistic game automata
• The knowledge complexity of interactive proof-systems
• Probabilistic automata