Multi-oracle interactive protocols with constant space verifiers (Q1190986)

It is known that the process of generalization of the original (one- prover) interactive proof system notion into the multi-prover one followed two different paths, thus resulting into two models -- the one where all provers cooperate with each other, and the one where provers oppose each other with at least one trying to help the verifier (and the other trying to mislead him). The paper deals with the power of constant space probabilistic verifiers in both these multi-prover models. Using an ingenious digital signature, a protocol by which a finite state verifier simulates a Turing machine in both opposing provers model as well as collaborating provers model is presented. The result for the opposing provers model is then used to prove undecidability of the question whether a player in a reasonable game of imperfect information has a probabilistic strategy which wins with probability greater than \(0.5\).