Now showing items 2-2 of 2

    • Upper Bounds on the Complexity of Space Bounded Interactive Proofs 

      Condon, Anne; Lipton, Richard J (University of Wisconsin-Madison Department of Computer Sciences, 1989)
      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 ...