About This Item

Ask the MINDS@UW Librarian

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

Search and browse




About MINDS@UW

Deposit materials

  1. Register to deposit in MINDS@UW
  2. Need deposit privileges? Contact us.
  3. Already registered? Have deposit privileges? Deposit materials.