6533b85afe1ef96bd12b9e68

RESEARCH PRODUCT

Finite State Verifiers with Constant Randomness

A. C. Cem SayAbuzer Yakaryilmaz

subject

Discrete mathematicsFinite-state machine010102 general mathematics0102 computer and information sciencesGas meter prover01 natural sciencesRegular language010201 computation theory & mathematicsBounded functionProbabilistic automaton0101 mathematicsConstant (mathematics)Time complexityRandomnessMathematics

description

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.

yearjournalcountryeditionlanguage
2012-01-01
https://doi.org/10.1007/978-3-642-30870-3_65