4 ms·
Huh? Assuming I understand your comment correctly, that is, not what that paper is showing. That paper is showing that if the verifier has polynomial time comp
by drdeca 3y ago
Huh? Assuming I understand your comment correctly, that is, not what that paper is showing.
That paper is showing that if the verifier has polynomial time computational power, with two provers who each have unlimited computational power, and who have some shared quantum entanglement, are communicating individually with the prover, and the prover also has access to randomness and such, then there is a protocol that can allow the provers to, for any recursively enumerable language, demonstrate to the verifier, for any string, whether that string is in that language.
RE is a WAY bigger class than what the verifier can compute alone.
And, is also way bigger than the without-entanglement version, MIP.
That paper is showing that adding quantum entanglement to the setup for MIP, allows for way more problems to be in the class.
- l33t7332273 3y ago>RE is a WAY bigger class than what the verifier can compute alone I always think of the RE(CE) sets as those that are possible to compute. I’m aware that RE sets are not computable, but since RE sets are those accepted by a turing machine, I still consider that set to be the “main” one when speaking informally. Maybe this is misguided
- drdeca 3y agothe verifier in the MIP* setup/definition is assumed to be limited to a polynomial amount of computation.