Have I somehow moved over into a different universe? "We show that the class MIP* of languages that can be decided [...] is equal to the class RE of recursively enumerable languages. " Kidding, right? RIGHT?! https://arxiv.org/abs/2001.04383
-
-
I think that depends on the "number of questions" being finite.
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
I got pointed to this as further reading, cleared up a lot of things for me:https://quantumfrontiers.com/2020/03/01/the-shape-of-mip-re/ …
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
The prover in interactive proof classes (including quantum and multi versions) has unlimited computation power. The limits are on the verifier, message lengths, randomness, how many messages, etc. Often helps you prove weaker versions of the conjecture you really care about.
-
In MIP there are multiple unlimited-power provers that can't communicate, the verifier cross checks them. MIP* lets them share quantum information with each other. The provers are always oracle-ish in power, but untrustworthy so they have to convince/prove to you.
End of conversation
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.