The complexity of debate checking
From MaRDI portal
Publication:493647
DOI10.1007/s00224-014-9547-7zbMath1329.68108OpenAlexW2080131634MaRDI 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
Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Real-time, constant-space, constant-randomness verifiers, Unnamed Item, Real-time, constant-space, constant-randomness verifiers, Debates with Small Transparent Quantum Verifiers, Constant-space, constant-randomness verifiers with arbitrarily small error
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
