Interactive proof systems with polynomially bounded strategies
Anne Condon, Richard E. Ladner · 2003
Interactive proof systems in which the prover is restricted to have a polynomial size strategy are investigated. The restriction of polynomial-size computation tree, or logarithmically bounded number of coin flips, guarantees a polynomial-size strategy. One result is that interactive proof systems in which the prover is restricted to a polynomial-size strategy are equivalent to MA, Merlin-Arthur games, of L. Babai and S. Moran (1988). 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. A logarithmic number of coin flips is equivalent to NP, even when logarithmic space is added as a restriction.>