Finite state verifiers with constant randomness

Details Finite state verifiers with constant randomness Finite state verifiers with constant randomness

2011-02-14

arxiv.org/abs/1102.2719v1

Computer Science

Computational Complexity

12 pages

Scientific paper

We give a new certificate-based characterization of $\mathsf{NL}$, as the class of languages whose members have certificates that can be verified with small error in polynomial time by probabilistic finite automata (2pfa's) which have access to only a constant number of random bits. We obtain this result by demonstrating that verifiers which are restricted to have this property are equivalent in language recognition power to multihead finite automata. The cases where the verifier is restricted in different manners in its input and certificate head movements are also examined.

Affiliated with

Also associated with

No associations

Rating

Finite state verifiers with constant randomness does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Finite state verifiers with constant randomness, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finite state verifiers with constant randomness will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-215365