ECCC-Report TR13-004https://eccc.weizmann.ac.il/report/2013/004Comments and Revisions published for TR13-004en-usWed, 02 Jan 2013 21:09:21 +0200
Paper TR13-004
| Finite state verifiers with constant randomness |
A. C. Cem Say,
Abuzer Yakaryilmaz
https://eccc.weizmann.ac.il/report/2013/004We 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.Wed, 02 Jan 2013 21:09:21 +0200https://eccc.weizmann.ac.il/report/2013/004