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 (3)

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of the max word problem and the power of one-way interactive proof systems