Upper Bounds on the Complexity of Space Bounded Interactive Proofs

Abstract

We show that the class IP(2pfa) of languages accepted by interactive proof systems with finite state verifiers is contained in ATIME(2 2o(n)). We also show that 2-prover interactive proof systems with finite state verifiers accept exactly the recursive languages. Our results generalize to other space bounds. We also obtain some results of independent interest on the rate of convergence of time-varying Markov chains and of non-Markov chains, called feedback chains, to their halting states.