6 ms·

Can someone offer a layman summary? Very curious but everything at this link and links in the comments is relatively impenetrable to me.

by edge17 6y ago

mlthoughts2018 6y ago
RE (recursively enumerable) is the class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time. Keep that pinned in your mind. IP: The class of decision problems for which a "yes" answer can be verified by an interactive proof. Here a probabilistic polynomial-time verifier sends messages back and forth with an all-powerful prover. There are some additional stipulations about the probability with which the verifier must accept or reject the prover’s claim. MIP* is like IP but (a) you can have multiple provers and (b) the provers can share arbitrarily many entangled qubits. MIP* = RE One way to look at this is to think of MIP* as a subset of RE and then RE as a subset of MIP. RE being contained within MIP* isn’t very surprising - if it’s already in RE, then just clone a bunch of entangled copies of the “regular” Turing machine that already verifies “yes” answers in finite time and you’ve got your no-op MIP* version of the same thing. The hard part here (and where all the details that make the proof such an impressive achievement come in) is how to ensure the verifier doesn’t have to just trust the provers, for any general problem in RE, while still only running in polynomial time to achieve a certain level of probability of correctness. MIP* \in RE is weird though. Any decision problem where a verifier can polynomially verify a “yes” answer given info from multiple entangled provers must also be a problem where there exists a “regular” Turing machine that can verify a “yes” answer in finite time. What’s surprising is that the “collusion” of multiple entangled provers never presents the verifier with something they can polynomially verify such that some other “regular” Turing machine couldn’t. You don’t “get more” or “get extra” out of their being multiple provers that can “work together” in a sense. It turns out to be no different than the class of problems where a “yes” answer was already easy (finite time) to verify. One careful point to note is that the only place in this where polynomial time comes into play is the process of the verifier validating a “yes” answer from the provers in MIP. The process of the provers themselves may not be polynomial (though, for “yes” answers it is clear it must be finite). RE problems are not necessarily efficiently verifiable. For example the Halting Problem itself is in RE. The finite verifier for a “yes” answer is to run for the finite amount of time it takes to halt for that example. The MIP interactive proof could be running several of those in parallel and just ignore any entanglement and ask each one “have you halted?” They will all wait around for the finite amount of time it takes to halt and then say “yes” and the verifier can just check they all said yes (O(n) where n is number of provers). But again the trick is how to modify that algorithm so the verifier doesn’t just have to believe the provers, and the authors of the proof give that explicitly for the Halting Problem on page 154 of the paper. Side note: it’s really hard writing prose with a term that needs an asterisk on HN - apologies for weird italics and “MIP” when it should be “MIP*”.
- lisper 6y ago
  > the Halting Problem itself is in RE This is a little misleading. The set of TMs that halt is in RE. But the halting problem requires you to construct the complement of this set, and that is not in RE.
  - mlthoughts2018 6y ago
    You are incorrect, in fact the Halting Problem is RE-complete, https://en.m.wikipedia.org/wiki/RE_(complexity) https://en.m.wikipedia.org/wiki/RE_(complexity)
    - lisper 6y ago
      I don't see how your citation supports your position: "In computability theory and computational complexity theory, RE (recursively enumerable) is the class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time." But the halting problem requires you to produce a YES OR NO answer within a finite time. That's the whole point.
      - mlthoughts2018 6y ago
        It’s right there: > “ Examples of RE-complete problems: > Halting problem: Whether a program given a finite input finishes running or will run forever.”
        lisper 6y ago
        Ah. Well, that's just a mistake. It's a misleading use of the term "the halting problem." There is a problem which is a variant of the halting problem which is RE-complete, namely, the problem of determining whether a given program halts. But that is not THE Halting problem, it is merely a halting problem. THE Halting Problem is the problem of determining whether a program halts OR DOES NOT HALT, and THAT problem is famously not in RE.

Can someone offer a layman summary? Very curious but everything at this link and links in the comments is relatively impenetrable to me.

by edge17 6y ago

Can someone offer a layman summary? Very curious but everything at this link and links in the comments is relatively impenetrable to me.

mlthoughts2018 6y ago

RE (recursively enumerable) is the class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time. Keep that pinned in your mind. IP: The class of decision problems for which a "yes" answer can be verified by an interactive proof. Here a probabilistic polynomial-time verifier sends messages back and forth with an all-powerful prover. There are some additional stipulations about the probability with which the verifier must accept or reject the prover’s claim. MIP* is like IP but (a) you can have multiple provers and (b) the provers can share arbitrarily many entangled qubits. MIP* = RE One way to look at this is to think of MIP* as a subset of RE and then RE as a subset of MIP. RE being contained within MIP* isn’t very surprising - if it’s already in RE, then just clone a bunch of entangled copies of the “regular” Turing machine that already verifies “yes” answers in finite time and you’ve got your no-op MIP* version of the same thing. The hard part here (and where all the details that make the proof such an impressive achievement come in) is how to ensure the verifier doesn’t have to just trust the provers, for any general problem in RE, while still only running in polynomial time to achieve a certain level of probability of correctness. MIP* \in RE is weird though. Any decision problem where a verifier can polynomially verify a “yes” answer given info from multiple entangled provers must also be a problem where there exists a “regular” Turing machine that can verify a “yes” answer in finite time. What’s surprising is that the “collusion” of multiple entangled provers never presents the verifier with something they can polynomially verify such that some other “regular” Turing machine couldn’t. You don’t “get more” or “get extra” out of their being multiple provers that can “work together” in a sense. It turns out to be no different than the class of problems where a “yes” answer was already easy (finite time) to verify. One careful point to note is that the only place in this where polynomial time comes into play is the process of the verifier validating a “yes” answer from the provers in MIP. The process of the provers themselves may not be polynomial (though, for “yes” answers it is clear it must be finite). RE problems are not necessarily efficiently verifiable. For example the Halting Problem itself is in RE. The finite verifier for a “yes” answer is to run for the finite amount of time it takes to halt for that example. The MIP interactive proof could be running several of those in parallel and just ignore any entanglement and ask each one “have you halted?” They will all wait around for the finite amount of time it takes to halt and then say “yes” and the verifier can just check they all said yes (O(n) where n is number of provers). But again the trick is how to modify that algorithm so the verifier doesn’t just have to believe the provers, and the authors of the proof give that explicitly for the Halting Problem on page 154 of the paper. Side note: it’s really hard writing prose with a term that needs an asterisk on HN - apologies for weird italics and “MIP” when it should be “MIP*”.

lisper 6y ago
> the Halting Problem itself is in RE This is a little misleading. The set of TMs that halt is in RE. But the halting problem requires you to construct the complement of this set, and that is not in RE.
- mlthoughts2018 6y ago
  You are incorrect, in fact the Halting Problem is RE-complete, https://en.m.wikipedia.org/wiki/RE_(complexity) https://en.m.wikipedia.org/wiki/RE_(complexity)
  - lisper 6y ago
    I don't see how your citation supports your position: "In computability theory and computational complexity theory, RE (recursively enumerable) is the class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time." But the halting problem requires you to produce a YES OR NO answer within a finite time. That's the whole point.
    - mlthoughts2018 6y ago
      It’s right there: > “ Examples of RE-complete problems: > Halting problem: Whether a program given a finite input finishes running or will run forever.”
      - lisper 6y ago
        Ah. Well, that's just a mistake. It's a misleading use of the term "the halting problem." There is a problem which is a variant of the halting problem which is RE-complete, namely, the problem of determining whether a given program halts. But that is not THE Halting problem, it is merely a halting problem. THE Halting Problem is the problem of determining whether a program halts OR DOES NOT HALT, and THAT problem is famously not in RE.