2
$\begingroup$

The paper On The Power of Multi-prover Interactive Protocols by Fortnow, Rompel, Sipser states the following:

  1. There are provers $P_1, P_2, \dots, P_k$ in a multi-prover interactive proof system such that $k$ is polynomial in the size of the input. The value of $k$ cannot exceed a polynomial because this would prevent the verifier in the system from accessing all the provers.
  2. In one round a verifier can interact with more than one prover.

Since a verifier can interact with more than one prover in one round, is the real reason that the number of provers must be polynomial due to the fact that the total length of the messages to all the provers in one round must be polynomial in the length of the input?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Yes. We could have defined MIP to allow an exponential number of provers but that is basically the PCP model which is equivalent to MIP with a polynomial (or just two) provers.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.