Upper Bounds on the Complexity of Space Bounded Interactive Proofs
File(s)
Date
1989Author
Condon, Anne
Lipton, Richard J
Publisher
University of Wisconsin-Madison Department of Computer Sciences
Metadata
Show full item recordAbstract
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.
Permanent Link
http://digital.library.wisc.edu/1793/59112Citation
TR841