![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Entry tags:
The best thing since sliced bread: the Arthur-Merlin protocol
I think this has to do with statistics/probability. This is being discussed at ![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-community.gif)
ontd_merlin, and I could not resist making my own entry about it. And the Arthur-Merlin protocol also involves coins...seriously. As if we need any more reason why Arthur and Merlin are destined to be together. LOL
Excerpts from the wiki entry (source: http://en.wikipedia.org/wiki/Arthur%E2%80%93Merlin_protocol):
In computational complexity theory, an Arthur–Merlin protocol is an interactive proof system in which the verifier's coin tosses are constrained to be public (i.e. known to the prover too).
~ The basic assumption is that Arthur is a standard computer (or verifier) equipped with a random number generating device, while Merlin is effectively an oracle with infinite computational power (also known as a prover); but Merlin is not necessarily honest, so Arthur must analyze the information provided by Merlin in response to Arthur's queries and decide the problem itself.
Me: Sooo, Merlin's an oracle (of course, he has to be ~ magical ~ in some way lol!) and he's not "necessarily honest" like he's not being honest with Arthur about the whole magic thing.
Does anyone else see fic ideas forming? Merlin and Arthur are stuck inside a computer and need to heavily depend on each other to get out of the evil, bent on world domination super computer?? IDEK. It's late, and I'm feeling silly and stressed out... this is the result. :p
~ The simplest such protocol is the 1-message protocol where Merlin sends Arthur a message, and then Arthur decides whether to accept or not by running a probabilistic polynomial time computation. (This is similar to the verifier-based definition of NP, the only difference being that Arthur is allowed to use randomness here.) Merlin does not have access to Arthur's coin tosses in this protocol, since it is a single message protocol and Arthur tosses his coins only after receiving Merlin's message. This protocol is called MA. (aka M/A for Merlin/Arthur slash brought to you by computational complexity theory)
Me: Coins! OMG. Coins. ILU Arthur-Merlin protocol. Muahaha. *dies of laughter*
ontd_merlin, and I could not resist making my own entry about it. And the Arthur-Merlin protocol also involves coins...seriously. As if we need any more reason why Arthur and Merlin are destined to be together. LOL Excerpts from the wiki entry (source: http://en.wikipedia.org/wiki/Arthur%E2%80%93Merlin_protocol):
In computational complexity theory, an Arthur–Merlin protocol is an interactive proof system in which the verifier's coin tosses are constrained to be public (i.e. known to the prover too).
~ The basic assumption is that Arthur is a standard computer (or verifier) equipped with a random number generating device, while Merlin is effectively an oracle with infinite computational power (also known as a prover); but Merlin is not necessarily honest, so Arthur must analyze the information provided by Merlin in response to Arthur's queries and decide the problem itself.
Me: Sooo, Merlin's an oracle (of course, he has to be ~ magical ~ in some way lol!) and he's not "necessarily honest" like he's not being honest with Arthur about the whole magic thing.
Does anyone else see fic ideas forming? Merlin and Arthur are stuck inside a computer and need to heavily depend on each other to get out of the evil, bent on world domination super computer?? IDEK. It's late, and I'm feeling silly and stressed out... this is the result. :p
~ The simplest such protocol is the 1-message protocol where Merlin sends Arthur a message, and then Arthur decides whether to accept or not by running a probabilistic polynomial time computation. (This is similar to the verifier-based definition of NP, the only difference being that Arthur is allowed to use randomness here.) Merlin does not have access to Arthur's coin tosses in this protocol, since it is a single message protocol and Arthur tosses his coins only after receiving Merlin's message. This protocol is called MA. (aka M/A for Merlin/Arthur slash brought to you by computational complexity theory)
Me: Coins! OMG. Coins. ILU Arthur-Merlin protocol. Muahaha. *dies of laughter*