Talk:Arthur–Merlin protocol

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Mid-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Mid Priority
 Field:  Discrete mathematics
WikiProject Computer science (Rated Start-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 

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)

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