2 ms·
MIP*=Re
- nine_k 7y agoKey quotation, it appears: * There is a protocol by which two entangled provers can convince a polynomial-time verifier of the answer to any computable problem whatsoever (!!), or indeed that a given Turing machine halts.* I wonder what kind of limitations are posed on such provers (which the article calls "all-powerful").
- karmakaze 7y agoThis lecture[0] gives a good description of MIP and MIP* and how the poly(n) verifier is permitted to communicate with them. [0] https://www.youtube.com/watch?v=DmPA5FfLd6k https://www.youtube.com/watch?v=DmPA5FfLd6k