Constant-space, constant-randomness verifiers with arbitrarily small strong error

Abstract

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 a strong error bound strictly less than 1/2 is precisely NL, but their construction yields verifiers with strong error bounds that are very close to 1/2 for most languages in that class. We characterize a subset of NL for which verification with arbitrarily low strong error is possible by these extremely weak machines. It turns out that, for any " > 0, one can construct a constant-coin, constant-space verifier operating within strong error " 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 lineartime 2nfa(k)’s to simultaneous time-space complexity classes defined in terms of Turing machines.