Upper Bounds on the Complexity of Space Bounded Interactive Proofs
Show full item record
File(s):
- Author(s)
-
Condon, Anne; Lipton, Richard J
- Publisher
- University of Wisconsin-Madison Department of Computer Sciences
- Date
- Mar 15, 2012
- Abstract
- 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.
- Permanent link
-
http://digital.library.wisc.edu/1793/59112
- Export
-
Export to RefWorks
Part of
Show full item record
