<h3>Completely classical case (MIP)</h3>

<p>If the verifier is classical and there is no prior entanglement among provers, your class contains BPP∪NP and is contained in <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aM#ma" rel="noreferrer">MA</a>.</p>

<p>It is trivial that BPP is a lower bound.  To show that the class contains NP, consider the standard two-prover one-round interactive proof system for 3-colorability with perfect completeness and soundness error 1−1/poly.  If you want to reduce the soundness error to a constant, combine this with the PCP theorem.</p>

<p>As for the upper bound, the following stronger statement holds: MIP with the restriction that the total message length from the verifier to each prover is O(log <i>n</i>) is equal to MA.  This is because a strategy of each prover can be described by a string of polynomial length.</p>

<p>Interestingly, another upper bound exists when the system has perfect completeness.  Namely, multi-prover interactive proof systems with perfect completeness with O(log <i>n</i>)-bit total communication recognize at most <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aP#pnplog" rel="noreferrer">P<sup>NP[log]</sup></a>, and this holds even if we allow unbounded soundness error.  To prove this in the case of two provers, let <i>x</i><sub><i>s</i></sub> be the concatenation of all answers given by the first prover when the concatenation of all questions to the first prover is <i>s</i>, and define <i>y</i><sub><i>t</i></sub> analogously for the second prover.  To be accepted by the verifier with certainty, these variables <i>x</i><sub><i>s</i></sub> and <i>y</i><sub><i>t</i></sub> must satisfy certain constraints, and note that this is a 2CSP.  There are at most poly(<i>n</i>) choices for tuples (<i>s</i>, <i>t</i>, <i>x</i><sub><i>s</i></sub>, <i>y</i><sub><i>t</i></sub>), and for each choice, we can use the NP oracle to test whether the verifier rejects that tuple.  Therefore, with the NP oracle, we can list up all the constraints on the variables <i>x</i><sub><i>s</i></sub> and <i>y</i><sub><i>t</i></sub> in polynomial time.  Finally, we use the NP oracle once more to test whether there is an assignment to these variables which satisfies all the constraints.  Although this algorithm uses the NP oracle polynomially many times, all the queries except for the last one can be made in parallel, and therefore this can be converted to a P<sup>NP[log]</sup> algorithm.  The case of more than two provers is analogous.</p>

<p>This upper bound implies that although every MA system can be turned to one with perfect completeness, we cannot hope for a multi-prover interactive proof system with perfect completeness with O(log <i>n</i>)-bit communication unless MA⊆P<sup>NP[log]</sup>.  I do not know how unlikely the inclusion MA⊆P<sup>NP[log]</sup> is, but I just note that <a href="http://www.math.ucdavis.edu/~greg/zoology/relations.html#delta2p" rel="noreferrer">Complexity Zoology</a> states that there is an oracle relative to which BPP⊈<a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aP#pnp" rel="noreferrer">P<sup>NP</sup></a> (and therefore clearly MA⊈P<sup>NP[log]</sup>).</p>

<p>(In the case of single prover, Theorem 2 of Goldreich and Håstad [GH98] implies that IP with the total message length O(log <i>n</i>) bits is equal to BPP.)</p>

<p><strong>Added</strong>.  A necessary and sufficient characterization is as follows.</p>

<p>To explain this characterization, we need a variant of the notion of Karp reducibility (polynomial-time many-one reducibility).  For two decision problems <i>A</i> and <i>B</i>, let’s say that <i>A</i> is FP<sup>BPP</sup>-reducible to <i>B</i> (I know, this is an awful name) when there is a deterministic polynomial-time Turing machine <i>M</i> with access to the BPP oracle which maps yes-instances to yes-instances and no-instances to no-instances, where we allow “non-smart” oracle access (meaning that <i>M</i> can make a query to the BPP oracle about an instance which does not satisfy the promise of the BPP problem, in which case then oracle returns yes or no arbitrarily).  Then it can be proved that the following conditions on a problem <i>A</i> are equivalent.</p>

<p>(i) <i>A</i> has a multi-prover interactive proof system with O(log <i>n</i>)-bit communication and two-sided bounded error.<br>
(ii) <i>A</i> has a two-prover one-round interactive proof system with O(log <i>n</i>)-bit communication, exponentially small completeness error, and constant soundness error.<br>
(iii) <i>A</i> is FP<sup>BPP</sup>-reducible to a problem in NP.</p>

<p>(Proof idea: Implication (ii)⇒(i) is trivial.  Implication (i)⇒(iii) can be obtained in a similar way to the above proof in the case of one-sided error.  Implication (iii)⇒(ii) follows from the PCP theorem because the class of problems satisfying condition (ii) is closed under FP<sup>BPP</sup>-reducibility.)</p>

<h3>Classical verifier with entangled provers (MIP*)</h3>

<p>Next consider the case with a classical verifier and entangled provers.  In this case, the class with bounded error again contains BPP∪NP.</p>

<p>Kempe, Kobayashi, Matsumoto, Toner, and Vidick [KKMTV11] shows that every problem in NP has a three-prover one-round interactive proof system with perfect completeness and soundness error 1−1/poly where the total length of messages is O(log <i>n</i>) bits, and the soundness holds against entangled provers.  Therefore, MIP* with total message length O(log <i>n</i>) bits and bounded error contains NP.  A later result by Ito, Kobayashi, and Matsumoto [IKM09] (shameless plug) reduces the number of provers from three to two.  The case of constant soundness is open at the top of my knowledge.</p>

<p>It is not known whether MIP* with total message length O(log <i>n</i>) bits is contained in the class R of decidable problems or not, and this question is equivalent to whether MIP*⊆R (another open problem) by the padding argument.</p>

<h3>References</h3>

<p>[GH98] Oded Goldreich and Johan Håstad.  On the complexity of interactive proofs with bounded communication.  <em>Information Processing Letters</em>, 67(4):205–214, Aug. 1998.  <a href="http://dx.doi.org/10.1016/S0020-0190%2898%2900116-1" rel="noreferrer">http://dx.doi.org/10.1016/S0020-0190%2898%2900116-1</a></p>

<p>[IKM09] Tsuyoshi Ito, Hirotada Kobayashi, and Keiji Matsumoto.  Oracularization and two-prover one-round interactive proofs against nonlocal strategies.  <em>Proceedings: Twenty-Fourth Annual IEEE Conference on Computational Complexity (CCC 2009)</em>, 217–228, July 2009.  <a href="http://dx.doi.org/10.1109/CCC.2009.22" rel="noreferrer">http://dx.doi.org/10.1109/CCC.2009.22</a></p>

<p>[KKMTV11] Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, and Thomas Vidick.  Entangled games are hard to approximate.  <em>SIAM Journal on Computing</em>, 40(3):848–877, 2011.  <a href="http://dx.doi.org/10.1137/090751293" rel="noreferrer">http://dx.doi.org/10.1137/090751293</a></p>

CC BY-SA 3.0
2011-09-30T09:50:09.747Z
Great, thanks Tsuyoshi, this is exactly what I was looking for.
Joe Fitzsimons
CC BY-SA 3.0
2011-09-30T12:31:24.173Z
So the last classical problem open is to decide whether this complexity class is equal to MA.
Peter Shor 
CC BY-SA 3.0
2011-09-30T12:48:17.473Z
@Peter: Yes.  I had considered this problem for a while, but I do not have an answer.
Tsuyoshi Ito
CC BY-SA 3.0
2011-10-01T22:37:48.743Z
I found my old note stating that O(1)-prover one-round MIP systems with perfect completeness with O(log n)-bit communication is unlikely to contain MA.  I added this argument to the answer in revision 3.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-17T23:22:42.307Z
For more about the oracle relative to which BPP⊈P^NP mentioned in this answer, see [this question](http://cstheory.stackexchange.com/questions/8997/oracle-relative-to-which-mathsfbpp-is-not-contained-in-2-mathsfp).
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-29T23:17:39.350Z
2011-10-06T17:47:46.213Z
2011-10-06T17:47:46.213Z
Tsuyoshi Ito
<p>Beigi, Shor and Watrous have a very nice <a href="http://arxiv.org/abs/1004.0411" rel="nofollow">paper</a> on the power of quantum interactive proofs with short messages. They consider three variants of 'short messages', and the specific one I care about is their second variant where any number of messages can be sent, but the total message length must be logarithmic. In particular they show that such interactive proof systems have the expressive power of BQP.</p>

<p>What I want to know is whether there are analogous results for the multi-prover setting, either for classical or quantum verifiers. Are any non-trivial complexity results known for multi-prover interactive proofs where the total length of all messages is restricted to be logarithmic in the problem size?</p>

CC BY-SA 3.0
2011-09-21T11:35:00.310Z
If the provers are allowed to share a prior entanglement of arbitrary size, then the class is not known to be inside the class R of decidable problems (even when the verifier is classical).  Showing your class is contained in R is equivalent to showing MIP* is in R.  As for lower bound, I do not think that anything better than the single-prover counterpart is known.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-21T11:40:20.543Z
@TsuyoshiIto: Even for short classical messages?
Joe Fitzsimons
CC BY-SA 3.0
2011-09-21T11:41:17.460Z
“Decidable” does not depend on the size, so you can use padding argument to show the equivalence.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-21T11:45:12.800Z
Ah yes, I see. That's a nice observation and answers my question as far as quantum goes. However, for the classical case, it is necessarily contained in NEXP. Any idea if there is any results there?
Joe Fitzsimons
CC BY-SA 3.0
2011-09-21T15:17:35.763Z
Sounds like something needs to be converted to an answer
Suresh Venkat
CC BY-SA 3.0
2011-09-21T15:32:10.560Z
The question asks about many different settings, and I do not have time to check the relevant literature and write a full-fledged answer right now.  If anyone wants to write an answer, please go ahead
Tsuyoshi Ito
<cc.complexity-theory><quantum-computing><interactive-proofs>
What is known about multi-prover interactive proofs with short messages?
Joe Fitzsimons
# What is known about multi-prover interactive proofs with short messages?

(Asked by: username_0 on 2011-09-21)

Beigi, Shor and Watrous have a very nice [paper](http://arxiv.org/abs/1004.0411) on the power of quantum interactive proofs with short messages. They consider three variants of 'short messages', and the specific one I care about is their second variant where any number of messages can be sent, but the total message length must be logarithmic. In particular they show that such interactive proof systems have the expressive power of BQP.

What I want to know is whether there are analogous results for the multi-prover setting, either for classical or quantum verifiers. Are any non-trivial complexity results known for multi-prover interactive proofs where the total length of all messages is restricted to be logarithmic in the problem size?

**Tags:** cc.complexity-theory, quantum-computing, interactive-proofs

> **Comments:**
> **username_1**: If the provers are allowed to share a prior entanglement of arbitrary size, then the class is not known to be inside the class R of decidable problems (even when the verifier is classical).  Showing your class is contained in R is equivalent to showing MIP* is in R.  As for lower bound, I do not think that anything better than the single-prover counterpart is known.  
> **username_0**: @TsuyoshiIto: Even for short classical messages?  
> **username_1**: “Decidable” does not depend on the size, so you can use padding argument to show the equivalence.  
> **username_0**: Ah yes, I see. That's a nice observation and answers my question as far as quantum goes. However, for the classical case, it is necessarily contained in NEXP. Any idea if there is any results there?  
> **username_2**: Sounds like something needs to be converted to an answer  
> **username_1**: The question asks about many different settings, and I do not have time to check the relevant literature and write a full-fledged answer right now.  If anyone wants to write an answer, please go ahead  

---

## 1 answers

### Answer by username_1 on 2011-09-29. Score: 13 | Accepted answer

### Completely classical case (MIP)

If the verifier is classical and there is no prior entanglement among provers, your class contains BPP∪NP and is contained in [MA](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aM#ma).

It is trivial that BPP is a lower bound. To show that the class contains NP, consider the standard two-prover one-round interactive proof system for 3-colorability with perfect completeness and soundness error 1−1/poly. If you want to reduce the soundness error to a constant, combine this with the PCP theorem.

As for the upper bound, the following stronger statement holds: MIP with the restriction that the total message length from the verifier to each prover is O(log *n*) is equal to MA. This is because a strategy of each prover can be described by a string of polynomial length.

Interestingly, another upper bound exists when the system has perfect completeness. Namely, multi-prover interactive proof systems with perfect completeness with O(log *n*)-bit total communication recognize at most [PNP[log]](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aP#pnplog), and this holds even if we allow unbounded soundness error. To prove this in the case of two provers, let *x**s* be the concatenation of all answers given by the first prover when the concatenation of all questions to the first prover is *s*, and define *y**t* analogously for the second prover. To be accepted by the verifier with certainty, these variables *x**s* and *y**t* must satisfy certain constraints, and note that this is a 2CSP. There are at most poly(*n*) choices for tuples (*s*, *t*, *x**s*, *y**t*), and for each choice, we can use the NP oracle to test whether the verifier rejects that tuple. Therefore, with the NP oracle, we can list up all the constraints on the variables *x**s* and *y**t* in polynomial time. Finally, we use the NP oracle once more to test whether there is an assignment to these variables which satisfies all the constraints. Although this algorithm uses the NP oracle polynomially many times, all the queries except for the last one can be made in parallel, and therefore this can be converted to a PNP[log] algorithm. The case of more than two provers is analogous.

This upper bound implies that although every MA system can be turned to one with perfect completeness, we cannot hope for a multi-prover interactive proof system with perfect completeness with O(log *n*)-bit communication unless MA⊆PNP[log]. I do not know how unlikely the inclusion MA⊆PNP[log] is, but I just note that [Complexity Zoology](http://www.math.ucdavis.edu/~greg/zoology/relations.html#delta2p) states that there is an oracle relative to which BPP⊈[PNP](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aP#pnp) (and therefore clearly MA⊈PNP[log]).

(In the case of single prover, Theorem 2 of Goldreich and Håstad [GH98] implies that IP with the total message length O(log *n*) bits is equal to BPP.)

**Added**. A necessary and sufficient characterization is as follows.

To explain this characterization, we need a variant of the notion of Karp reducibility (polynomial-time many-one reducibility). For two decision problems *A* and *B*, let’s say that *A* is FPBPP-reducible to *B* (I know, this is an awful name) when there is a deterministic polynomial-time Turing machine *M* with access to the BPP oracle which maps yes-instances to yes-instances and no-instances to no-instances, where we allow “non-smart” oracle access (meaning that *M* can make a query to the BPP oracle about an instance which does not satisfy the promise of the BPP problem, in which case then oracle returns yes or no arbitrarily). Then it can be proved that the following conditions on a problem *A* are equivalent.

(i) *A* has a multi-prover interactive proof system with O(log *n*)-bit communication and two-sided bounded error.  
(ii) *A* has a two-prover one-round interactive proof system with O(log *n*)-bit communication, exponentially small completeness error, and constant soundness error.  
(iii) *A* is FPBPP-reducible to a problem in NP.

(Proof idea: Implication (ii)⇒(i) is trivial. Implication (i)⇒(iii) can be obtained in a similar way to the above proof in the case of one-sided error. Implication (iii)⇒(ii) follows from the PCP theorem because the class of problems satisfying condition (ii) is closed under FPBPP-reducibility.)

### Classical verifier with entangled provers (MIP\*)

Next consider the case with a classical verifier and entangled provers. In this case, the class with bounded error again contains BPP∪NP.

Kempe, Kobayashi, Matsumoto, Toner, and Vidick [KKMTV11] shows that every problem in NP has a three-prover one-round interactive proof system with perfect completeness and soundness error 1−1/poly where the total length of messages is O(log *n*) bits, and the soundness holds against entangled provers. Therefore, MIP\* with total message length O(log *n*) bits and bounded error contains NP. A later result by Ito, Kobayashi, and Matsumoto [IKM09] (shameless plug) reduces the number of provers from three to two. The case of constant soundness is open at the top of my knowledge.

It is not known whether MIP\* with total message length O(log *n*) bits is contained in the class R of decidable problems or not, and this question is equivalent to whether MIP\*⊆R (another open problem) by the padding argument.

### References

[GH98] Oded Goldreich and Johan Håstad. On the complexity of interactive proofs with bounded communication. *Information Processing Letters*, 67(4):205–214, Aug. 1998. <http://dx.doi.org/10.1016/S0020-0190%2898%2900116-1>

[IKM09] username_1, Hirotada Kobayashi, and Keiji Matsumoto. Oracularization and two-prover one-round interactive proofs against nonlocal strategies. *Proceedings: Twenty-Fourth Annual IEEE Conference on Computational Complexity (CCC 2009)*, 217–228, July 2009. <http://dx.doi.org/10.1109/CCC.2009.22>

[KKMTV11] Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, and Thomas Vidick. Entangled games are hard to approximate. *SIAM Journal on Computing*, 40(3):848–877, 2011. <http://dx.doi.org/10.1137/090751293>

> **Comments:**
> **username_0**: Great, thanks Tsuyoshi, this is exactly what I was looking for.  
> **username_3**: So the last classical problem open is to decide whether this complexity class is equal to MA.  
> **username_1**: @Peter: Yes.  I had considered this problem for a while, but I do not have an answer.  
> **username_1**: I found my old note stating that O(1)-prover one-round MIP systems with perfect completeness with O(log n)-bit communication is unlikely to contain MA.  I added this argument to the answer in revision 3.  
> **username_1**: For more about the oracle relative to which BPP⊈P^NP mentioned in this answer, see [this question](http://cstheory.stackexchange.com/questions/8997/oracle-relative-to-which-mathsfbpp-is-not-contained-in-2-mathsfp).  

---

