Interactive Proof Systems with Polynomially Bounded Strategies

摘要

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. 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 MP, and when logarithmic space is added as a restriction, the power is not diminished. The proof that NP ⊆ of or equal to IP (log-space, log-random-bits) illustrates an interesting application of the new "fingerprinting" method of Lipton. Public interactive proof systems which have polynomial size strategies are also investigated.