Constant-Space, Constant-Randomness Verifiers with Arbitrarily Small Error

M. Utkan Gezer, A. C. Cem Say

We study the capabilities of probabilistic finite-state machines that act as verifiers for certificates of language membership for input strings, in the regime where the verifiers…