Interactive Proof Systems with Polynomially Bounded Strategies

Interactive Proof Systems with Polynomially Bounded Strategies

Abstarct

Interactive proof systems in which the Prover is restricted to have a
polynomial size strategy are investigated. The restriction of
polynomial size computation tree, visible to the Prover, or
logarithmically bounded number of coin flips by the Verifier guarantee
a polynomial size strategy. The additional restriction of logarithmic
space is also investigated. A main result of the paper is that
interactive proof systems in which the Prover is restricted to a
polynomial size strategy are equivalent to MA, Merlin-Arthur games,
defined by Babai and Moran [1]. Polynomial tree size is also
equivalent to MA, but when logarithmic space is added as a
restriction, the power of polynomial tree size reduces to NP.
Logarithmically bounded number of coin flips are equivalent to NP, and
When logarithmic space is added as a restriction, the power is not
diminished. The proof that NP subseteq IP(log-space,
log-random-bits) illustrates an interesting application of the new
``fingerprinting'' method of Lipton [14]. Public interactive proof
systems which have polynomial size strategies are also investigated.