The complexity of debate checking
type: Item
instance of: scholarly article
title: The complexity of debate checking
zbMATH Open document ID: 1329.68108
author: H. Gökalp Demirci
author: A. C. Cem Say
author: Abuzer Yakaryılmaz
published in: Theory of Computing Systems
publication date: 2015-09-04T00:00:00Z
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q10
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 6478530
zbMATH Keywords: incomplete information debates
zbMATH Keywords: private alternation
zbMATH Keywords: games
zbMATH Keywords: probabilistic computation
MaRDI profile type: Publication
full work available at URL: s00224-014-9547-7
OpenAlex ID: W2080131634
cites work: Two-way finite automata with quantum and classical states.
cites work: Computational Complexity
cites work: Proof verification and the hardness of approximation problems
cites work: Non-deterministic exponential time has two-prover interactive protocols
cites work: Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
cites work: On non-determinacy in simple computing devices
cites work: Alternation
cites work: Space-bounded probabilistic game automata
cites work: The complexity of the max word problem and the power of one-way interactive proof systems
cites work: Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions
cites work: Interactive proof systems with polynomially bounded strategies
cites work: Finite state verifiers I
cites work: Zero-knowledge proofs of identity
cites work: Q4527018
cites work: Propositional dynamic logic of regular programs
cites work: Q3947125
cites work: Alternating multihead finite automata
cites work: Alternation in interaction
cites work: Q3355236
cites work: Multihead two-way probabilistic finite automata
cites work: Q5414546
cites work: The complexity of two-player games of incomplete information
cites work: Finite State Verifiers with Constant Randomness
cites work: IP = PSPACE
cites work: Q3392275
cites work: Unbounded-error quantum computation with small space bounds
cites work: Quantum Alternation
DOI: 10.1007/S00224-014-9547-7
Recommended article: Efficient Probabilistically Checkable Debates
Recommended article: Argumentation in multi-issue debates
Recommended article: Credible debate equilibria
Recommended article: Debates and decisions: On a rationale of argumentation rules.
Recommended article: Empirical Evaluation of Strategies for Multiparty Argumentative Debates
Recommended article: Q4583949
Recommended article: Verifying Refutations with Extended Resolution
description: scientific article; zbMATH DE number 6478530