Upper Bounds on the Complexity of Space Bounded Interactive Proofs
Anne Condon and Richard J Lipton
1989
We shoe 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.
Download this report (PDF)
Return to tech report index
|
