The complexity of debate checking

DOI10.1007/s00224-014-9547-7zbMath1329.68108MaRDI QIDQ493647

A. C. Cem Say, Abuzer Yakaryılmaz, H. Gökalp Demirci

Publication date: 4 September 2015

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-014-9547-7

zbMATH Keywords

gamesincomplete information debatesprivate alternationprobabilistic computation

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

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

Related Items

Unnamed Item, Debates with Small Transparent Quantum Verifiers, Real-time, constant-space, constant-randomness verifiers, Constant-space, constant-randomness verifiers with arbitrarily small error, Real-time, constant-space, constant-randomness verifiers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unbounded-error quantum computation with small space bounds
• Multihead two-way probabilistic finite automata
• Non-deterministic exponential time has two-prover interactive protocols
• The complexity of two-player games of incomplete information
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Zero-knowledge proofs of identity
• Alternating multihead finite automata
• Propositional dynamic logic of regular programs
• The complexity of the max word problem and the power of one-way interactive proof systems
• Two-way finite automata with quantum and classical states.
• Interactive proof systems with polynomially bounded strategies
• On non-determinacy in simple computing devices
• Finite State Verifiers with Constant Randomness
• Proof verification and the hardness of approximation problems
• Alternation
• Finite state verifiers I
• IP = PSPACE
• Space-bounded probabilistic game automata
• Quantum Alternation
• Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions
• Computational Complexity
• Computational Complexity
• Alternation in interaction