Constant-Coin Complete-Information Debates for with Arbitrarily Small Strong Error
En palabras de los autores
We study complete-information debate systems in which a probabilistic finite-state verifier reads the alternating messages of a prover and a refuter. Demirci, Say, and Yakary{\i}lmaz showed that every language in has such debates checkable with a constant number of random bits and arbitrarily small weak error. Their strong-error construction, which also counts nontermination as failure, did not permit arbitrary error reduction. We close this gap: for every and every , there is a constant-space verifier using a constant number of private coin tosses that has perfect completeness and strong error at most . The verifier simulates a polynomial-time alternating multihead finite automaton, privately spot-checking one of its input heads. The key observation is that, on a nonmember, the refuter may concede any round in which the prover first misreports a head reading. This ensures termination against every prover when the refuter follows the specified strategy, and permits strong-error reduction by repetition.
Apareció: martes, 22 de septiembre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 11 pages