3 ms·
What this means is that, if you are confronted by a group of people, traditionally called provers, and you limit their collaboration in a certain way (here, by
by lidHanteyk 7y ago
What this means is that, if you are confronted by a group of people, traditionally called provers, and you limit their collaboration in a certain way (here, by entangling some qubits and only using the entangled state for "communication"), then they can nonetheless prove to you in an interactive discussion that they know how to solve some Halting-equivalent problem.
This does not give provers any new tricks for solving hard problems. This puts a ceiling on the power of this sort of prover-and-verifier proof and what it can show. There are problems harder than Halting (that is, that are hard even with oracles for Halting [0]) and MIP* doesn't contain them.
[0] https://en.wikipedia.org/wiki/Turing_jump https://en.wikipedia.org/wiki/Turing_jump