On the complexity of space bounded interactive proofs
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 462-467
- https://doi.org/10.1109/sfcs.1989.63519
Abstract
Two results on interactive proof systems with two-way probabilistic finite-state verifiers are proved. The first is a lower bound on the power of such proof systems if they are not required to halt with high probability on rejected inputs: it is shown that they can accept any recursively enumerable language. The second is an upper bound on the power of interactive proof systems that halt with high probability on all inputs. The proof method for the lower bound also shows that the emptiness problem for one-way probabilistic finite-state machines is undecidable. In the proof of the upper bound some results of independent interest on the rate of convergence of time-varying Markov chains to their halting states are obtained.<>Keywords
This publication has 4 references indexed in Scilit:
- Multi-oracle interactive protocols with space bounded verifiersPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Probabilistic game automataJournal of Computer and System Sciences, 1988
- Multi-prover interactive proofs: how to remove intractabilityPublished by Association for Computing Machinery (ACM) ,1988
- Multiple-person alternationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979