13
$\begingroup$

Beigi, Shor and Watrous have a very nice paper 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?

Improve this question
$\endgroup$
6
  • 5
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Sep 21, 2011 at 11:35
  • $\begingroup$ @TsuyoshiIto: Even for short classical messages? $\endgroup$
    – Joe Fitzsimons
    Sep 21, 2011 at 11:40
  • 1
    $\begingroup$ “Decidable” does not depend on the size, so you can use padding argument to show the equivalence. $\endgroup$
    – Tsuyoshi Ito
    Sep 21, 2011 at 11:41
  • 1
    $\begingroup$ 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? $\endgroup$
    – Joe Fitzsimons
    Sep 21, 2011 at 11:45
  • $\begingroup$ Sounds like something needs to be converted to an answer $\endgroup$
    – Suresh Venkat
    Sep 21, 2011 at 15:17

1 Answer 1

Reset to default
12
+100
$\begingroup$

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.

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], and this holds even if we allow unbounded soundness error. To prove this in the case of two provers, let xs 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 yt analogously for the second prover. To be accepted by the verifier with certainty, these variables xs and yt must satisfy certain constraints, and note that this is a 2CSP. There are at most poly(n) choices for tuples (s, t, xs, yt), 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 xs and yt 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 states that there is an oracle relative to which BPP⊈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] Tsuyoshi Ito, 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

Improve this answer
$\endgroup$
5
  • $\begingroup$ Great, thanks Tsuyoshi, this is exactly what I was looking for. $\endgroup$
    – Joe Fitzsimons
    Sep 30, 2011 at 9:50
  • 4
    $\begingroup$ So the last classical problem open is to decide whether this complexity class is equal to MA. $\endgroup$
    – Peter Shor
    Sep 30, 2011 at 12:31
  • $\begingroup$ @Peter: Yes. I had considered this problem for a while, but I do not have an answer. $\endgroup$
    – Tsuyoshi Ito
    Sep 30, 2011 at 12:48
  • 2
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Oct 1, 2011 at 22:37
  • $\begingroup$ For more about the oracle relative to which BPP⊈P^NP mentioned in this answer, see this question. $\endgroup$
    – Tsuyoshi Ito
    Nov 17, 2011 at 23:22

Your Answer

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

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