Jump to content

Talk:Arthur–Merlin protocol

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Source to check information: MIT course on advanced complexity. Andris 21:04, May 19, 2004 (UTC)

BPP verifier?

[edit]

I just removed the following sentence:

 However, Arthur is not necessarily a BPP verifier as it is not known whether MA is contained in the class .[1]

I had two reasonds: first, it is nowhere explained what a BPP verifier is, so this sentence was coming out of the blue a bit. Second, it seems that for Arthur to be a BPP verifier, it suffices that ExistsBPP is contained in MA, which is known to be true. Therefore, the sentence seems to false too. However, without a proper definition of what it means to be a BPP verifier, I cannot be sure (coming back to the first issue), so I've removed the sentence instead of correcting it. Note that ExistsBPP is still mentioned in the 'Properties' section, where the statement seems to be correct.

--Sjcjoosten (talk) 11:03, 27 June 2017 (UTC)[reply]

References

  1. ^ "Complexity Zoo:E - Complexity Zoo". Complexityzoo.uwaterloo.ca. 2012-11-17. Retrieved 2016-07-26.

Example?

[edit]

Could someone please put examples of natural problems in MA? Note that non-specialists may look at this page, ones who are a bit shaky on the background necessary to be sure they understand just from looking at definitions

67.189.144.253 (talk) 18:19, 6 September 2020 (UTC)[reply]