On the power of interaction

LetIPf(n)] be the class of languages recognized by interactive proofs withf(¦x¦) interactions. Babai 2] showed that all languages recognized by interactive proofs with a bounded number of interactions can be recognized by interactive proofs with only two interactions; i.e., for every constantk, IPk] collapses toIP2].In this paper, we give evidence that interactive proofs with an unbounded number of interactions may be more powerful than interactive proofs with a bounded number of interactions. We show that for any polynomially bounded polynomial time computable functionf(n) and anyg(n)=o(f(n)) there exists an oracleB such thatIP ^B f(n)] ₌ IP ^B g(n)].The techniques employed are extensions of the techniques for proving lower bounds on small depth circuits used in 6], 14] and 10].Research done while in the Department of Mathematics at M. I. T. and supported by an ONR graduate fellowship.Supported in part by NSF Grant DCR MCS8509905.Research done while at the Laboratory for Computer Science at M. I. T. and Supported by an IBM fellowship.