1
$\begingroup$

Recently I was asking about the impact of the groundbreaking result MIP*=RE on logic and proof theory (see this discussion). Surprising as it is I got confused with the following: MIP* is a ,,quantum'' version of MIP where two provers are allowed to use only classical correlations. My intuition was that allowing more general correlations would always make provers more powerful: it turned out to be the case for quantum correlation but here it is claimed (somewhere in the discussion) that it was believed that MIP* would turn out to be smaller than MIP. And in fact allowing even stronger correlations, the so called non-signalling correlation we get another class $MIP_{ns}$ which turns out to be smaller than MIP: namely $MIP_{ns}=EXP$ while $MIP=NEXP$.

What is the intuitive reason behind this fact? Why allowing more general correlations won't give yet another bigger complexity class?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ In case you don't get enough attention here you might also like to post this here: cstheory.stackexchange.com which is a much smaller site but also exclusively focuses on theoretical cs research $\endgroup$
    – Sidharth Ghoshal
    Commented Oct 6, 2023 at 19:24
  • $\begingroup$ What I got from the Aaronson blog that you linked to is that, when you increase the provers' communication possibilities, you not only make it easier for honest provers to provide good answers but also make it easier for dishonest provers to cheat. The verifier needs to be convinced that they didn't cheat, and that becomes harder because of the increased means of communication. $\endgroup$
    – Andreas Blass
    Commented Oct 6, 2023 at 21:01
  • $\begingroup$ @AndreasBlass I'm not sure whether I understand the problem correctly: suppose that I am the verifier, there are two quantum provers and we will be playing with the halting problem. So I take a Turing machine $M$, I don't know whether it halts but provers do know this. They can decide either option: to convince me rightly or to trick me (they can decide to trick me in both cases: if the machine eventually halts or if the machine will never halt). If they will always be honest and I will know that they will be then increasing the set of correlations (i.e. increasing their communication... $\endgroup$
    – truebaran
    Commented Oct 7, 2023 at 9:28
  • $\begingroup$ ... power) would result in the fact that they will be able to convince me of even more instances (assumed always true). However if they can also lie, at some point their communication power is so large that they can force me to believe something which is not true: the class of problems where they cannot trick me is for non-signalling correlations equal to EXP. Is it correct way of thinking? $\endgroup$
    – truebaran
    Commented Oct 7, 2023 at 9:35
  • $\begingroup$ @truebaran Your two comments are essentially correct, but I think that, when the provers' power increases, you (the verifier) will have to adjust your acceptance algorithm to take into account the provers' greater ability to cheat. And such an adjustment is available only for a lower complexity class of problems. $\endgroup$
    – Andreas Blass
    Commented Oct 7, 2023 at 16:53

0

Reset to default

You must log in to answer this question.