Constant space verifiers check every P problem with tiny error
Constant-Coin Complete-Information Debates for $\mathsf{P}$ with Arbitrarily Small Strong Error
Computational ComplexityFormal Languages and Automata Theory
Summary
This paper looks at how a simple computing device can check back-and-forth arguments about problems that can be solved quickly on computers. The authors improve previous work by making it so that the verifier, which uses only a little memory and a few coin flips, can be almost certain when it accepts or rejects. They show how the verifier can handle tricky cases where the arguments might never end, ensuring it always finishes and can make errors as small as desired. This strengthens our understanding of how efficiently computers can verify solutions to problems.
What this means in practice
- •For complexity theory developers: Build more efficient verification protocols for polynomial-time problems with guaranteed low error using minimal memory.
- •For formal verification engineers: Design lightweight decision procedures that handle interactive challenges while guaranteeing termination and low error.
A theory result. No direct application yet.
Authors
M. Utkan Gezer
Abstract
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ılmaz showed that every language in $\mathsf{P}$ 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 $L\in\mathsf{P}$ and every $\varepsilon>0$, there is a constant-space verifier using a constant number of private coin tosses that has perfect completeness and strong error at most $\varepsilon$. 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.