Paper Info
Title
Finite state verifiers with constant randomness
Abstract
We give a new characterization of NL as the class of languages whose members have certificates that can be verified with small error in polynomial time by finite state machines that use a constant number of random bits, as opposed to its conventional description in terms of deterministic logarithmic-space verifiers. It turns out that allowing two-way interaction with the prover does not change the class of verifiable languages, and that no polynomially bounded amount of randomness is useful for constant-memory computers when used as language recognizers, or public-coin verifiers. A corollary of our main result is that the class of outcome problems corresponding to O(log n)-space bounded games of incomplete information where the universal player is allowed a constant number of moves equals NL.
Year
DOI
Venue
2014
10.2168/LMCS-10(3:6)2014
LOGICAL METHODS IN COMPUTER SCIENCE
Keywords
DocType
Volume
interactive proof systems,randomness complexity,constant randomness,probabilistic finite automata,multihead automata,NL
Journal
10
Issue
ISSN
Citations 
3
1860-5974
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
A. C. Cem Say119326.13
Abuzer Yakaryilmaz216825.31