Constant-Space, Constant-Randomness Verifiers with Arbitrarily Small Error
For complexity theorists, it refines the understanding of verification with extremely limited resources, showing a trade-off between error and language class.
The paper characterizes a subset of NL for which constant-space, constant-randomness verifiers can achieve arbitrarily small error, showing that languages recognizable by linear-time multi-head nondeterministic finite automata (2nfa(k)) can be verified with error ε for any ε>0. It also relates the power of these automata to simultaneous time-space complexity classes.
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 are restricted to toss some fixed nonzero number of coins regardless of the input size. Say and Yakaryılmaz showed that the class of languages that could be verified by these machines within an error bound strictly less than $1/2$ is precisely NL, but their construction yields verifiers with error bounds that are very close to $1/2$ for most languages in that class when the definition of "error" is strengthened to include looping forever without giving a response. We characterize a subset of NL for which verification with arbitrarily low error is possible by these extremely weak machines. It turns out that, for any $\varepsilon>0$, one can construct a constant-coin, constant-space verifier operating within error $\varepsilon$ for every language that is recognizable by a linear-time multi-head nondeterministic finite automaton (2nfa($k$)). We discuss why it is difficult to generalize this method to all of NL, and give a reasonably tight way to relate the power of linear-time 2nfa($k$)'s to simultaneous time-space complexity classes defined in terms of Turing machines.